{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Satellite Constellation Optimization (GA+QA).ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "machine_shape": "hm",
      "authorship_tag": "ABX9TyMJ40I3rm7iVfyQ8YvfqrHy",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/dsskonuru/satellite-constellation-optimization-ga-qa/blob/master/Satellite_Constellation_Optimization_(GA%2BQA).ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "h7ViiJiaNwOc",
        "colab_type": "code",
        "outputId": "e11db488-b647-4fcc-f9c6-1439760a84b8",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 315
        }
      },
      "source": [
        "!pip install dimod\n",
        "!pip install networkx \n",
        "!pip install dwave-neal"
      ],
      "execution_count": 1,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Collecting dimod\n",
            "\u001b[?25l  Downloading https://files.pythonhosted.org/packages/3c/b8/4810e966bb986c167142405b90cc7d35bdb16de54713f1f7fb00822c1119/dimod-0.9.2-cp36-cp36m-manylinux1_x86_64.whl (4.8MB)\n",
            "\u001b[K     |████████████████████████████████| 4.8MB 2.8MB/s \n",
            "\u001b[?25hRequirement already satisfied: numpy<2.0.0,>=1.16.0 in /usr/local/lib/python3.6/dist-packages (from dimod) (1.18.4)\n",
            "Installing collected packages: dimod\n",
            "Successfully installed dimod-0.9.2\n",
            "Requirement already satisfied: networkx in /usr/local/lib/python3.6/dist-packages (2.4)\n",
            "Requirement already satisfied: decorator>=4.3.0 in /usr/local/lib/python3.6/dist-packages (from networkx) (4.4.2)\n",
            "Collecting dwave-neal\n",
            "\u001b[?25l  Downloading https://files.pythonhosted.org/packages/c6/14/964a6a7aff39d97fbcb9ff82a4525a484d301468048a706be3dcc5be64ca/dwave_neal-0.5.4-cp36-cp36m-manylinux1_x86_64.whl (390kB)\n",
            "\u001b[K     |████████████████████████████████| 399kB 2.8MB/s \n",
            "\u001b[?25hRequirement already satisfied: six<2.0.0,>=1.11.0 in /usr/local/lib/python3.6/dist-packages (from dwave-neal) (1.12.0)\n",
            "Requirement already satisfied: numpy<2.0.0,>=1.14.0 in /usr/local/lib/python3.6/dist-packages (from dwave-neal) (1.18.4)\n",
            "Requirement already satisfied: dimod>=0.7.7 in /usr/local/lib/python3.6/dist-packages (from dwave-neal) (0.9.2)\n",
            "Installing collected packages: dwave-neal\n",
            "Successfully installed dwave-neal-0.5.4\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "-kgOeH_lV_iB",
        "colab_type": "text"
      },
      "source": [
        ">$\\text{Ising:} \\qquad  E(\\bf{s}|\\bf{h},\\bf{J})\n",
        "= \\left\\{ \\sum_{i=1}^N h_i s_i + \\sum_{i<j}^N J_{i,j} s_i s_j  \\right\\}$\n",
        "\n",
        ">$\\small E \\quad {\\longrightarrow} \\quad Objective \\; function \\; (to \\; be \\; minimized) \n",
        "\\\\ \\small s_i \\quad {\\longrightarrow} \\quad Subconstellation \n",
        "\\\\ \\small h_i \\quad {\\longrightarrow} \\quad Coverage \\; of \\; the \\; subconstellation\n",
        "\\\\ \\small J_{i,j} \\quad {\\longrightarrow} \\quad Penality \\; for \\; pairs \\; having \\; a \\; satellite \\; in \\; common$"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "7BtJ36FN2Nh-",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "import numpy as np\n",
        "import matplotlib.pyplot as plt\n",
        "import itertools\n",
        "import networkx as nx\n",
        "\n",
        "import dimod\n",
        "import neal"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "bIfQnA_BFGC3",
        "colab_type": "text"
      },
      "source": [
        "### Complexity of the problem"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "z_qNqwKQm9T7",
        "colab_type": "text"
      },
      "source": [
        "Suppose you have a set of ``N`` satellites and ``k`` targets on Earth that you\n",
        "want to observe. Each of your satellites has varying capabilities for Earth\n",
        "observation; in particular, the amount of ground that they can observe for a\n",
        "set amount of time is different. Since there are ``k`` targets, you would like\n",
        "to have ``k`` constellations to monitor said targets. \n",
        "\n",
        "Note: We are assuming that ``N`` is a multiple of ``k``."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "s9x4cMuqF6mw",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "N = 12\n",
        "k = 4 # number of targets\n",
        "\n",
        "subconstellation_size = N // k  # satellites per constellation"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "eiRaFJ9neMqc",
        "colab_type": "text"
      },
      "source": [
        "Each of the 12 satellites (labelled 0-11) has a coverage score. This could be calculated as the percentage of time  that the Earth region is in range of the satellite. We are assuming a random value in this case, this can be replaced by real values in a particular application."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kZ3VdUrQIkLq",
        "colab_type": "code",
        "outputId": "d7f8e28c-a18c-4e3b-a2a1-a3b33362ed1c",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "coverage = {}\n",
        "for i in range(N):\n",
        "  np.random.seed(i)\n",
        "  coverage[i] = np.random.randint(0, 100)/100\n",
        "print(coverage)"
      ],
      "execution_count": 105,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "{0: 0.44, 1: 0.37, 2: 0.4, 3: 0.24, 4: 0.46, 5: 0.99, 6: 0.1, 7: 0.47, 8: 0.67, 9: 0.92, 10: 0.09, 11: 0.25}\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "h-PDBnozJA36",
        "colab_type": "code",
        "outputId": "f3520435-6275-4ac7-f80a-f121a3565805",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 279
        }
      },
      "source": [
        "score_threshold = 0.5\n",
        "lists = sorted(coverage.items()) # sorted by key, return a list of tuples\n",
        "x, y = zip(*lists) # unpack a list of pairs into two tuples\n",
        "plt.xlabel(\"Satellite #\")\n",
        "plt.ylabel(\"Coverage\")\n",
        "plt.hlines(score_threshold, 0, N, linestyles='dashed', colors='r')\n",
        "plt.bar(x, y, align='edge')\n",
        "plt.show()"
      ],
      "execution_count": 29,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYIAAAEGCAYAAABo25JHAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+j8jraAAAVi0lEQVR4nO3dfbgedX3n8fdHAhXEgprAWhIN1oiyrg0YQaGLWKDlSdAFFVZcsWioigut4hWQuha7SMVWVgtofCgWXR6K2gYJIihIrwpIeBBMEIgUTZCWBPGhRVTc7/5xD/XkPCQ3J/ecOyfzfl3XuTIzv7lnvpOcnM+Z38z8JlWFJKm7njTsAiRJw2UQSFLHGQSS1HEGgSR1nEEgSR03Y9gFPFEzZ86suXPnDrsMSZpWbr755rVVNWu8tmkXBHPnzmXZsmXDLkOSppUk35uoza4hSeo4g0CSOs4gkKSOay0Iknw6yYNJvj1Be5J8JMnKJLcn2b2tWiRJE2vzjOB84MD1tB8EzGu+FgLntViLJGkCrQVBVV0H/HA9qxwO/G313ABsn+SZbdUjSRrfMK8R7ASsGjG/ulkmSZpC0+JicZKFSZYlWbZmzZphlyNJm5VhBsH9wJwR87ObZWNU1eKqWlBVC2bNGvfBOEnSJA3zyeIlwAlJLgL2BH5cVQ8MsR5txuYuunyg27vvzEMGuj1pmFoLgiQXAvsCM5OsBv4XsCVAVX0MWAocDKwEHgHe1FYtkqSJtRYEVXX0BtoLeHtb+5ck9WdaXCyWJLXHIJCkjjMIJKnjDAJJ6jiDQJI6ziCQpI4zCCSp4wwCSeo4g0CSOs4gkKSOMwgkqeOGOfqopI5zVNhNg2cEktRxBoEkdZxBIEkdZxBIUscZBJLUcQaBJHWcQSBJHWcQSFLHGQSS1HEGgSR1nEEgSR1nEEhSxxkEktRxBoEkdZxBIEkdZxBIUscZBJLUcQaBJHWcQSBJHWcQSFLHGQSS1HGtBkGSA5PclWRlkkXjtD8ryTVJbk1ye5KD26xHkjRWa0GQZAvgHOAgYFfg6CS7jlrtNOCSqtoNOAo4t616JEnja/OMYA9gZVXdW1W/AC4CDh+1TgG/2UxvB/ygxXokSeNoMwh2AlaNmF/dLBvpfcAxSVYDS4F3jLehJAuTLEuybM2aNW3UKkmdNeyLxUcD51fVbOBg4IIkY2qqqsVVtaCqFsyaNWvKi5SkzVmbQXA/MGfE/Oxm2UjHAZcAVNX1wJOBmS3WJEkapc0guAmYl2TnJFvRuxi8ZNQ63wf2A0jyAnpBYN+PJE2h1oKgqh4DTgCuBO6kd3fQ8iSnJzmsWe2dwFuSfAu4EDi2qqqtmiRJY81oc+NVtZTeReCRy947YnoFsHebNUiS1m/YF4slSUNmEEhSxxkEktRxBoEkdZxBIEkdZxBIUscZBJLUcQaBJHWcQSBJHWcQSFLHGQSS1HEGgSR1nEEgSR1nEEhSxxkEktRxBoEkdZxBIEkdZxBIUscZBJLUcQaBJHWcQSBJHWcQSFLHzRh2AZI2PXMXXT7Q7d135iED3Z4GyzMCSeo4g0CSOs4gkKSOMwgkqeMMAknqOINAkjrOIJCkjjMIJKnjDAJJ6rgnFARJtmmrEEnScPQVBEn2SrIC+E4z/ztJzu3jcwcmuSvJyiSLJljntUlWJFme5P8+oeolSRut37GGPgz8AbAEoKq+lWSf9X0gyRbAOcABwGrgpiRLqmrFiHXmAacAe1fVw0l2mMQxSJI2Qt9dQ1W1atSiX23gI3sAK6vq3qr6BXARcPiodd4CnFNVDzf7eLDfeiRJg9FvEKxKshdQSbZM8i7gzg18ZidgZHisbpaN9DzgeUn+KckNSQ4cb0NJFiZZlmTZmjVr+ixZktSPfoPgj4C30/tBfj8wv5nfWDOAecC+wNHAJ5JsP3qlqlpcVQuqasGsWbMGsFtJ0uP6ukZQVWuB1z/Bbd8PzBkxP7tZNtJq4Maq+iXwz0nuphcMNz3BfUmSJqmvIEjykXEW/xhYVlX/MMHHbgLmJdmZXgAcBfz3Uev8Pb0zgb9JMpNeV9G9/dQkSRqMfruGnkyvO+ie5utF9H7DPy7J2eN9oKoeA04ArqR3PeGSqlqe5PQkhzWrXQk81Nyaeg1wclU9NOmjkSQ9Yf3ePvoierd4/gogyXnAPwK/C9wx0YeqaimwdNSy946YLuBPmi9J0hD0e0bwNGDbEfNPAZ7eBMPPB16VJGnK9HtG8EHgtiTXAgH2Ac5I8hTg6pZqkyRNgX7vGvpUkqX0HhIDOLWqftBMn9xKZZKkKfFEBp17FHgAeBh47oaGmJAkTQ/93j76ZuBEencK3Qa8FLge+L32SpMkTYV+zwhOBF4CfK+qXgHsBvyotaokSVOm3yB4tKoeBUjyG1X1HWCX9sqSJE2Vfu8aWt2MAfT3wFVJHga+115ZkqSp0u9dQ69uJt+X5BpgO+DLrVUlSZoyGwyC5gUzy6vq+QBV9fXWq5IkTZkNXiNonh6+K8mzpqAeSdIU6/cawdOA5Um+Cfz74wur6rCJPyJJmg76DYI/bbUKSdLQ9Hux+OtJng3Mq6qrk2wDbNFuaZKkqdDvk8VvARYCTwd+m94rKz8G7NdeaS3Yd9+xy177Wnjb2+CRR+Dgg8e2H3ts72vtWjjyyLHtb30rvO51sGoVvOENY9vf+U545Svhrrvg+OPHtp92Guy/P9x2G5x00tj2M86AvfaCb3wDTj11bPvZZ8P8+XD11fDnfz62/eMfh112gcsug7/8y7HtF1wAc+bAxRfDeeeNbb/0Upg5E84/v/c12tKlsM02cO65cMklY9uvvbb354c+BF/60rptW28NV1zRm37/++GrX123/RnPgM9/vjd9yilw/fXrts+eDZ/9bG/6pJN6f4cjPe95sHgxAGd8+aM854frviBvxQ7P4fT9FwLw4cs+xDN/unad9lt2ej4ffPmxAJz3xTN42s9+8uvGG86C/faDP21Olg86CH72s3X3f+ih8K539aan2ffeRfc+xAf3eSO3zH4Bu6++k3df95kxHz99v4Ws2PE57H3fbbzjGxeNaT/1D07g3mfMZr+VN8K+Z43d/wUXAHDonddxzK1LxzS/9VWn8PA223HkHVdz5B1jx7Y89jXv49Etn8wxt1zOod/5x97CG0bsZxP53mPhQrj77nXb58/v/d8FOOYYWL163faXvQw+8IHe9BFHwEMPrXtMA9bvA2VvB/YGfgJQVfcAO7RSkSRpSqX3bpgNrJTcWFV7Jrm1qnZLMgO4pape1H6J61qwYEEtW7ZsqneraW7uossHur37zjxkoNvb1EzV35f/LlMnyc1VtWC8tn7PCL6e5FRg6yQHAH8HXDaoAiVJw9NvECwC1tB7LeXx9F4/eVpbRUmSpk6/t4++CvjbqvpEm8VIkqZev2cErwTuTnJBkkObawSSpM1Av88RvCnJlsBBwNHAOUmuqqo3t1qdpDG8wKpB6/s3+6r6ZZIrgAK2ptddZBBI0jTXV9dQkoOSnA/cAxwBfBL4Ty3WJUmaIv2eEfwP4GLg+Kr6eYv1qIPs6pCGq99rBEcn2RE4IAnAN6vqwVYrkyRNiX67hl4DfBN4DfBa4MYk4wx+IkmabvrtGjoNeMnjZwFJZgFXA5e2VZgkaWr0GwRPGtUV9BD9P4OwyRh0XzTYHy1p+us3CL6c5Ergwmb+dfSGmZAkTXPrDYIkzwV2rKqTk/w34HebpuuBz7VdnCSpfRs6IzgbOAWgqr4AfAEgyX9p2l7ZanWSpNZtqJ9/x6q6Y/TCZtncViqSJE2pDQXB9utp23pDG09yYJK7kqxMsmg96x2RpJKM+9IESVJ7NhQEy5r3Fa8jyZuBm9f3wSRbAOfQG6huV+DoJLuOs95TgROBG/stWpI0OBu6RnAS8MUkr+fXP/gXAFsBr97AZ/cAVlbVvQBJLgIOB1aMWu/9wF8AJz+BuiVJA7LeIKiqfwX2SvIK4IXN4sur6mt9bHsnYNWI+dXAniNXSLI7MKeqLk8yYRAkWQgsBHjWs57Vx643f47PI2lQ+h1r6BrgmkHuOMmTgL8Cju1j/4uBxdB7ef0g65Ckrmvz6eD7gTkj5mc3yx73VHpnGdcmuQ94KbDEC8aSNLXaDIKbgHlJdk6yFXAUsOTxxqr6cVXNrKq5VTUXuAE4rKqWtViTJGmU1oKgqh4DTgCuBO4ELqmq5UlOT3JYW/uVJD0xrb6EvqqWMmpMoqp67wTr7ttmLZKk8bUaBF3lHT2SppNpN5S0JGmwDAJJ6jiDQJI6ziCQpI4zCCSp4wwCSeo4g0CSOs4gkKSOMwgkqeMMAknqOINAkjrOIJCkjjMIJKnjDAJJ6jiDQJI6ziCQpI4zCCSp4wwCSeo4g0CSOs4gkKSOMwgkqeMMAknqOINAkjrOIJCkjjMIJKnjZgy7AEma7uYuunzg27zvzEMGvs2JeEYgSR3nGYEmNN1/y5HUH88IJKnjDAJJ6jiDQJI6ziCQpI5rNQiSHJjkriQrkywap/1PkqxIcnuSryZ5dpv1SJLGai0IkmwBnAMcBOwKHJ1k11Gr3QosqKoXAZcCH2yrHknS+No8I9gDWFlV91bVL4CLgMNHrlBV11TVI83sDcDsFuuRJI2jzSDYCVg1Yn51s2wixwFXjNeQZGGSZUmWrVmzZoAlSpI2iYvFSY4BFgBnjddeVYurakFVLZg1a9bUFidJm7k2nyy+H5gzYn52s2wdSfYH3gO8vKp+3mI9kqRxtHlGcBMwL8nOSbYCjgKWjFwhyW7Ax4HDqurBFmuRJE2gtSCoqseAE4ArgTuBS6pqeZLTkxzWrHYWsC3wd0luS7Jkgs1JklrS6qBzVbUUWDpq2XtHTO/f5v4lSRu2SVwsliQNj0EgSR1nEEhSxxkEktRxBoEkdZxBIEkdZxBIUscZBJLUcQaBJHWcQSBJHWcQSFLHGQSS1HEGgSR1nEEgSR1nEEhSx7X6PgKpS+Yuunzg27zvzEMGvk1pNM8IJKnjPCOQtFkb9Jna5niW5hmBJHWcQSBJHWcQSFLHGQSS1HEGgSR1nEEgSR1nEEhSxxkEktRxBoEkdZxBIEkdZxBIUscZBJLUcQaBJHWcQSBJHWcQSFLHtRoESQ5McleSlUkWjdP+G0kubtpvTDK3zXokSWO1FgRJtgDOAQ4CdgWOTrLrqNWOAx6uqucCHwb+oq16JEnja/OMYA9gZVXdW1W/AC4CDh+1zuHAZ5rpS4H9kqTFmiRJo6Sq2tlwciRwYFW9uZl/A7BnVZ0wYp1vN+usbua/26yzdtS2FgILm9ldgLsmWdZMYO0G15oePJZNz+ZyHOCxbKo25lieXVWzxmuYFu8srqrFwOKN3U6SZVW1YAAlDZ3HsunZXI4DPJZNVVvH0mbX0P3AnBHzs5tl466TZAawHfBQizVJkkZpMwhuAuYl2TnJVsBRwJJR6ywB3thMHwl8rdrqq5Ikjau1rqGqeizJCcCVwBbAp6tqeZLTgWVVtQT4FHBBkpXAD+mFRZs2untpE+KxbHo2l+MAj2VT1cqxtHaxWJI0PfhksSR1nEEgSR3XmSDY0HAX00WSOUmuSbIiyfIkJw67po2RZIsktyb50rBr2RhJtk9yaZLvJLkzycuGXdNkJfnj5nvr20kuTPLkYdfUrySfTvJg84zS48uenuSqJPc0fz5tmDX2Y4LjOKv5/ro9yReTbD+o/XUiCPoc7mK6eAx4Z1XtCrwUePs0PhaAE4E7h13EAPwf4MtV9Xzgd5imx5RkJ+B/Aguq6oX0bvRo+yaOQTofOHDUskXAV6tqHvDVZn5Tdz5jj+Mq4IVV9SLgbuCUQe2sE0FAf8NdTAtV9UBV3dJM/5TeD5ydhlvV5CSZDRwCfHLYtWyMJNsB+9C7C46q+kVV/Wi4VW2UGcDWzbM92wA/GHI9fauq6+jdgTjSyKFsPgO8akqLmoTxjqOqvlJVjzWzN9B7NmsguhIEOwGrRsyvZpr+8BypGa11N+DG4VYyaWcD7wb+37AL2Ug7A2uAv2m6uT6Z5CnDLmoyqup+4EPA94EHgB9X1VeGW9VG27GqHmim/wXYcZjFDMgfAlcMamNdCYLNTpJtgc8DJ1XVT4ZdzxOV5FDgwaq6edi1DMAMYHfgvKraDfh3pkf3wxhN//nh9MLtt4CnJDlmuFUNTvPA6rS+Zz7Je+h1EX9uUNvsShD0M9zFtJFkS3oh8Lmq+sKw65mkvYHDktxHr6vu95J8drglTdpqYHVVPX5mdim9YJiO9gf+uarWVNUvgS8Aew25po31r0meCdD8+eCQ65m0JMcChwKvH+QoDF0Jgn6Gu5gWmmG6PwXcWVV/Nex6JquqTqmq2VU1l96/x9eqalr+5llV/wKsSrJLs2g/YMUQS9oY3wdemmSb5nttP6bphe8RRg5l80bgH4ZYy6QlOZBeV+phVfXIILfdiSBoLrA8PtzFncAlVbV8uFVN2t7AG+j9Bn1b83XwsIsS7wA+l+R2YD5wxpDrmZTmrOZS4BbgDno/I6bNEA1JLgSuB3ZJsjrJccCZwAFJ7qF3xnPmMGvsxwTH8dfAU4Grmv/3HxvY/hxiQpK6rRNnBJKkiRkEktRxBoEkdZxBIEkdZxBIUscZBOqEJO9pRtS8vbn1bs8NrH9skt/qY7vnJzmymb42yYJmemkzIun2Sd62EXUfn+RNSeYn+fhktyOtj0GgzV4zJPShwO7NyI37s+7YU+M5lt4QC5NSVQc3A89tD0w6CID/ClwHvLz5Uxo4g0Bd8ExgbVX9HKCq1lbVDwCSvDfJTc3Y+4vTcySwgN4DYrcl2TrJi5N8PcnNSa58fMiCiSS5L8lMeg8v/XaznbOatpObfd6e5M8m+PwfJ7kNeDW94UT+DHjPIB8ikh5nEKgLvgLMSXJ3knOTvHxE219X1Uuasfe3Bg6tqkuBZfTGc5lPb4CvjwJHVtWLgU8D/7vPfS8CvltV86vq5CS/D8yjNzT6fODFSfYZ/aGq+jBwAL2hN+YDd1fVrlX1R5P5C5DWZ8awC5DaVlX/luTF9LpZXgFcnGRRVZ0PvCLJu+mNu/90YDlw2ahN7AK8kN6j/dB7WcsDTM7vN1+3NvPb0guG8bp9dge+leQ3gen8fgNt4gwCdUJV/Qq4Frg2yR3AG5NcBJxL721cq5K8DxjvtYwBllfVIF4/GeADVTXhhd8kO9A7i9kBeJTeoHxPbbqKjqiq7w6gDuk/2DWkzV6SXZLMG7FoPvA9fv1Df23zfocjR6zzU3oDfAHcBcxqLjqTZMsk/7nP3Y/cDvQGPvzDZn8k2an5wf8fqurBpjvoFnpdSJ8F3tR0LxkCGjjPCNQF2wIfbV72/RiwElhYVT9K8gng2/TeXHXTiM+cD3wsyc+Al9ELiY80r6WcQe/tahscwbaqHkryT+m9hPyK5jrBC4Drm26mfwOOYdQY+c17tp9RVWuT7AVM2yHHtelz9FFJ6ji7hiSp4wwCSeo4g0CSOs4gkKSOMwgkqeMMAknqOINAkjru/wNIgt23fasNvQAAAABJRU5ErkJggg==\n",
            "text/plain": [
              "<Figure size 432x288 with 1 Axes>"
            ]
          },
          "metadata": {
            "tags": [],
            "needs_background": "light"
          }
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "FPxBpGmbEnAw",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        },
        "outputId": "1ce33c25-1bf1-4357-fffe-06d250ee3816"
      },
      "source": [
        "import math\n",
        "\n",
        "def nCr(n,r):\n",
        "    f = math.factorial\n",
        "    return f(n) / f(r) / f(n-r)\n",
        "\n",
        "print('# possible subconstellations: ', nCr(12,3))"
      ],
      "execution_count": 103,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "# possible subconstellations:  220.0\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "jeqpVi32G6_V",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "import itertools\n",
        "\n",
        "subconstellations = {} # create dict of subconstellations and its coverage\n",
        "\n",
        "for subconstellation in itertools.combinations(range(N), N//k):\n",
        "    score = sum(coverage[v] for v in subconstellation) / subconstellation_size\n",
        "\n",
        "    if score < score_threshold:\n",
        "        continue\n",
        "\n",
        "    subconstellations[subconstellation] = score"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "bv70plghgr7Y",
        "colab_type": "text"
      },
      "source": [
        "The ``score_threshold`` is used to determine bad constellations. Constellations with coverage less than this value is not considered. It is assigned an arbitrarily picked number i.e `0.4`. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "dvvzrrAE53Vf",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        },
        "outputId": "873528e7-3f13-4467-d5f1-131377aca418"
      },
      "source": [
        "print('# subconstellations after search space pruning: ',len(subconstellations))"
      ],
      "execution_count": 107,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "# subconstellations after search space pruning:  134\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "bGQIcKHKFLJG",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "import networkx as nx\n",
        "\n",
        "G = nx.Graph()\n",
        "G.add_nodes_from(list(subconstellations.items()))\n",
        "\n",
        "for c0, c1 in itertools.combinations(list(subconstellations.keys()), 2):\n",
        "    if set(c0).isdisjoint(set(c1)):\n",
        "        G.add_edge(c0,c1)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "O0wZ7ynGFuMM",
        "colab_type": "code",
        "outputId": "0252c95a-f58d-464a-b8bb-12b071990e0d",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 319
        }
      },
      "source": [
        "nx.draw(G)"
      ],
      "execution_count": 33,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAb4AAAEuCAYAAADx63eqAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+j8jraAAAgAElEQVR4nO3dfXAUZ34n8G/PCzMjsBjzJl4Elo3AErsWnOH25HUWE2yCzXkrcRZnSU6Xze1VybV25WynKsdeuPioSrhaby7H7V3ZxR6V5LzWP7oiCeurZRPANnjPoD1jGxEMQoCQLS0gIYEQEpLQvNwf44aRNKOZfp6nu5/p/n6q9o/FMN2a0fSv+3l+L0Y6nU6DiIjIJwJunwAREZGTGPiIiMhXGPiIiMhXGPiIiMhXGPiIiMhXGPiIiMhXGPiIiMhXGPiIiMhXGPiIiMhXGPiIiMhXQm6fABHl1jc0hn0fd6Pt6iAGRxMoj4ZQs7Acz6+txNxZEbdPj6hkGezVSSTOjuDU2jWAN45cwNH2awCAsUTq7n+LhgJIA9jw8Hy8+EQ1Vi+Nq/gxiHyFgY+0UGpPN3YFp6aWTuw60IbRRBLTfTMNA4iGgtixpQYN9VWCP4V9Su3zJH9h4CNX2RVA7Lzw2hWcMq97FiPjqYJ/1xQLB7BjS602wY9Pq1QKGPjINXYEELsvvHYFp9auAWzb24KR8aTlc4qFg2hurEddpbuBxCtPq+R9wZ07d+50+yTIf6wGkEQqjeMd/YjHwnkv8E0tnXi5+STae28hkUojmUpPeY1kKo2OvmHsP3kZ8VjIUrBo7RrAy80nLQW9e+d+HetXzENFeTTn33ntndNo771l6XVNyXQaN4bv4Nm6xUL/XgU7Pk8iu7CcgRzX2jWAXQfaLAeQkfEUdh1ow6nugSn/7d6Fd/qnDQBIp4GR8SR2HTiLppbOoo//xpELGE1YfyIDgNFEEm8euZDzv/UNjeFo+7WC551POg28f+4a+ofGxF5Akh2fJ5GdGPjIcaoDiBMXXjuD076Pu8VeNIsBYN8nU1+nb2gMe45exCvNn+K7b32EV5o/xZ6jF5UGSbtuCIjswjo+cpTKAGImqai48O5pWDft31MZnF5Yv3zCn7ddHZywFyliNJFC25V7S6XT73Vexe7D7UqSTOz4PInsxsBHjlIdQJy68LZ23VAenEyDowmp1733OuMACieZjH75cxw804MP2vukkkzsvCEoBssmSAQDH1kie6FR/XRj94XXfHI6fLZH+jjAveCUrTyq5mtYHg1bSjLJ3usEIBT87HhaLYZTT7TkTQx8VBRVFxrVTzd2XniLTc+3ojwanvJnNQvLEQldlfo5oqEAymMhqb3Ousq45QxL1Z9nMZx8oiVvYnILFdTU0olte1tw6GwPxhKpKRfo0S//7OCZHmzb2zJtpqTKpxvAvguvlSzRYkVDAdQsum/Kn29dWyn92mkAn/ffdjzJRPXnWYgT2bvkfXzi8wGZ5UnVS2dL7y9D0ACSEsEkO4DYceEVzRItJA1g66NTg9y8WRE8sXI+Dp3tEQqyhgF8fflcHLvY73iSiaqn1Vw3BJPJZu+KPNGSNzHweZjs8qTKC415LkfOXZMKesDEAGLHhVcmSzQfwwB+/eH5eYPKSxuq8YvzfUKdW6KhIJbNKcOxi/1y5wjrSSZb11Zi9+F2qePmuyGYzInsXfIHLnV6lIrlSVX1Wdnncicp9xQ1OYCoWiY0L7yyWaL5RENBvLihOu9/X700jh1bahALW/tKZtqh1eDmyLgrSSbm06phiB2z0A2BqdSL/EkvDHwepGIfRNWF5sdHLyjdK5scQFRfeFVkiU5mBqdCy2wN9VXYsaUWsXCw4M9jGJkenWYPUDeSTEwvbahGNBQUOl6hGwKTnUX+5D9c6vQYVcuTKi406XQaf3GwHYmUmsenfAFEdpkw+8KrIkvUJNKMuaG+CnWVcbx55ALeP3cNBu5lKWbON9No+9cfno8XN1TffS9U7XVGggHsOXrR0n6w+bQq1ry78A0B4F7ZBHkTA5/HqNoHUXGhuSO7mfelQgFE5YVX1ZNTwAB+Y1XFhOBUrLrKOPY0rEP/0Bj2fdKNtiu3MDg6jvJoGDWL7sPWR6cGIRV7nQED+MezPXj3XK/l/WDzc7FrOoObT7TkPQx8HqJyH0TVhUbWjKCBjTULCgYQVRdeVU9OT39lId78V2ulXmPurEjRiSYqkkxSaQDpqVMtiq2LE31aLYbTZRPkbQx8HqJyH0TVhUZGKGDge08sx6ubHi7q76u48KrKEnW6W4hsSUQxiilXEXlaLYaTZRNOYbs197h/dSNlVO6DqLjQyEqk0vji+oilfyN74XUyPV81mb1OK4qpi7PytFqMUv5cJmO7Nfcx8HmIyn0QFRcaVeciQvTCq6KYvJj0fDuI7nWKcLourpQ/l2xst6YHBj7NyCx/qNwHcWLprNhzcZrKLFGnWdnrlOHGOCE7Pxcnlh2dbiBO+QV37ty50+2ToMzyx2vvnMZr73yGlo5+fHZ5EJf6htF29RZOdF7HX314Cacv38Sy+8uwcHY052t09t/GR53XpyQnWBENBfDN1Yux7oE5WDanDPtPXhYqRwgFDAQDBmQqGbLPxUkLZ0cRj4VwvKPf0s+eyRKtxaZVC208u8LqKuNYv2IebgzfQdeNEYQDxoSfIxoKIJ1OwzAyy3+iwgEDs8vCjn0+dnwuKr53xWjtGsDLzSctP4knUmkc77iO9SvmoaJc/Pg0EQOfBppaOvFy80m0995CIjU1q878s46+Yew/eRnxWCjn3krVvJn46w8vSQW+YMDAXz6/GmUzQlIXmj/atBK/vCQXhLPPxWl1lXHEY2Ec77iOZIHHpsnF5DqoKI/i2brF+L2vLcPssjDmz4pgSTyGNZVxfHP1YsyMhHC+d0jqGIlUGvNnRfD0V50L9Co/F1Xfu2K89s5ptPeK1RAm02ncGL6DZ+sWC/17mopLnS5TufxhLk8ePCM2Oy7XPohMmcAnXwyU9J6Mnen5Tsm31/ndtz5S8vpu1MWp+FycXHbklHr9MPC5SHW3+dauAdwcEb8Q5dsHEb3QlPJemcmu9Hy3lXpdnMzn4vSUB7en1NNUDHwuUtltPjtbTESh9lEiFxonWlk5RXV6vtu8Uhcn8rk4PeWB7db0w8DnEpXLHz8/fUU4hd1q+yirFxq7W1mRGC/VxVnhxrKjqjKjPk6WUIbTGVyiavnjv793Xmpoav2Dc9DcWG9roGmor0JzYz02r6pAJBRANDTx1y4aCiASCmDzqgrbz4UynBonpBs3pjyoWlb+8GIfXmg6gdauASWv52d84nOJquWPg2d6hJdtDACzY2FHlhS9uldWyrywB2uVG8uOqrogpdIsbFeFgU+SaOGrquWPnsFR8WUbOJ8t5rW9slLmpT3YYrkx5UFlFyQWtqvBwCdItt+eDk2gAWaL+Z3f9mDdyGa1owuSaIYpZXCPT0BTSye27W3BobM9GEukpixhjH75ZwfP9GDb3pYJk81NmeUPubc/YECqMwrAbDHy1x6siu+dSDarzJT6fMwMU7LOSKfd7MRYeqwUvprMlknZF4y+oTE8/vp7Uuv+hgEld5BP1izAX33nn8u/EJU8r+/BqvjeRUIBHNu+0fL7IXLtsOtc/E6P9bYSobLwVUW3+YXlEVy5KZ/izOGcZPL6HqybUx7saCDOrQoxXOq0QEXhazaZ5Y9oKIjfWLXQlWUbolIm+72TyWbNXlYOCJaSZONWhRgGviKpLHw1mVl1sbC1j8HMqvvDjSvETib7vFB6RchEMmS/d7LJJGZpz+PL50m9jsmNfqmljoGvSHYVvjbUV2HHllrEwsGCxcSTu837tQiZSJbM906VubNmKHkdblVY58s9PpHaO1WFr3/zYSfOXhmccDyZbvN+LEImUsHt6Rte6ZdainyV1Tl97V3mlzxf7d133/oI77X1KjuXfMcTyapTlWlK5FduZLO6mWHqd74JfNnTC0SKdF9p/hT7T15Wfl6qioJlfz4icl7j2yekMkw3r6qwNCmCMnwxgd3qE1Eilcbxjn7Es/pYdvbfxkedchPFrRzPqrrKONavmIcbw3fQdWME4YAxYWp6NBRAMGDgqdoF+OG36rBplXNTs4kot2VzyrD/5OUJ39VihQIG/vTZVXhg7kwbzszbPP/E19o1gG17W4T2wGLhIJob61FXGVeyLGHleDK8XoRM5CWihe2hgIFgwJi2NSLl5vnAp3IpQea1RI5HRP5Q7FZFLoW2L0Qb6XuZpwOf6s1jmadHkeMRkX+c6h64m2GaTKaQsHhlnpywJpPM53We3uP7yfHP0dLRL7UvFw4YmF0WxroH5mDh7CjisRCOd/QLrclbPR4R+UdFeRTP1i3G6srZ+GnrFcsN6DO5AtexfsU8HDpzFS83n0R77y0kUukp10Dzzzr6hrH/5GXEYyFfTXnwdB2fHUMn7ei3N93xiMhfmn75BZKCF5bRRBLf/7tTuNQ3XNSeoV/n+3m6c4tdQycLjXFRfTwi8gcVrRHPXLkl3Ej/VPeA2IFLjKcDn51DJ81+e8e2b8Srm1biuTVLUFGuZl+OLYiI/ElFa0RRfprv5+nA58TQSXOMy+5vr8G/+fqDnJZARMJUbM+IytVI36s8Hfi2rpWfOmBleoHTxyMib1G1PSMqVyN9L/J04HN6egGnJRCRDFXbM6L8klzniazO6Qo0nZ5ewGkJRCRKxcQGWX5IrivpAvZiCzQfnDsTbx3vdGx6AaclEJEIJ1ojFvLcmiXY/e01rh3fCSX7xFeoxY85V+vgmR5EQ0E8VVuBw2d7HZleYKXWj9MSiMhkbpfY2RpxOn5JrivJJz7RJ6o/+HoVLvUNOzZ0MrsFkdNDLomoNDnRGjEfv7RMLLnAp2LawpJ4LOf0go0PL8C7bb3Km7lyWgIRWSF6c//A3Jk413OL8/0KKLnAZ8fgRjZzJSLdiAyXfmRJXMkYNq8rqcCnetoCwMnlRKQvke0SJtcVVlLJLSra+ZgFmi+sX27pF8SvzVyJyD1ma0Qr2yWPLImjat5MnC2iHs/qDb1XZvuV1BPfK82fYv/Jy9Kv89yaJfiDr1dxSYCIPMXqQNtVi+7DD367ruC1zGvbQSXVuUXltIU3jlzAaEIsa8pPzVyJqDTcW8Eqflzapb7hghMZmlo6sW1vCw6d7cFYIjVlq2n0yz87eKYH2/a2oKmlU/AncE5JBT5V7XwiwYD06A+/NHMlIv21dg1g14E25eOIrATT7O0g3YNfSQU+VdMWbgs+6WXzSzNXItKfHStYdgVTHZRU4FM1/SAWDiqfzE5E5AYVw2tzrWB5eTuopALfvFkRPLZ8rvC/N6cfqOqD54dmrkSkN5XZ7ia7gqkuSibwtXYNoPHtE/jwQp/wa5jTD+yczE5E5CQVw2snr2DZEUx1UhJ1fFZTdHPJFGjWoK4yrmT0h1+auRKR3lRmu5vsCKY60f6JTyRFN5thZPb0srsScFI6EXmFHStYdgRTnWgd+ESzikzhoIHNqyrQ3Fg/oSsBJ6UTkVeoynbPXsHy+naQ1oFPJqsIAL5RPQ97Gtbl7Erw0oZqRENBodflpHQi0oUdK1h2BFOdaBv4ZLOKAODDi/15s4pWL41jx5YaxMLW3oLsvUIiIrfZsYLl9e0gbQOfE1lFDfVV2LGlFrFwsOAvTa69QiIiHahewfL6dpC2gc+prKKG+io0N9Zj86oKREIBRCc93kdDAURCgZx7hUREOrBjBcvL20HaljM4mVUkMvqDiEgn5k25qvmiZjAVm+2n93aQtoHPjayiubMieGH9ciXHJSJyWkN9Feoq45aH1073eoC6YKoLbQPf0vvLEDSApERyi85ZRUREdlC9gqU6mOpAu0G05sDDI+eu4U5Sbo8vEgrg2PaNXKYkIlLAK9tBWgU+Fa3JTIYBbF5VgT0N69ScHBERTdE3NIZ9H3ej7eogBkcTKI+GULOwHM+v1TcYahP47rUmUzM5IRYOormxviQeu4mISo25One0/RoATMjCN5c/Nzw8Hy8+UY3VS/W6DmsR+Fq7BrBtbwtGxuUHxAJmVhHr7YiI7FDs6pyuCS9aJLfItiYz6fomExF5hZXVuXQaGBlPYteBswCgzXXZ9cCnojUZAMwIGthYs6BksoqIiEqN6OCAkfEUdh1oQ11lXIvrs+uBT0VrslDAwPeeWI5XNz2s4IyIiPzDSnKKzOrcaCKJN49c0CLh0PXAp6I1WSKVxhfXRxSdERGR902fnHIVuw+3T0hOkV2dS6eB989dQ//QmOvZnq4HPq8PPCQi0k2h5BSzQP3gmR580N6HHVtqMDSmIA8DmcEBbnfIcj3weX3gIRGRTkSTU1ZU3OfI4AAnuD6dwesDD4mIdCGTnHL6VzeVnIMOq3OuBr7WrgEc7+iXvovQeeAhEZEuZJJTUooqvnVYnXNtqTN7jVmG7gMPiYh0oKp0TIYuq3OuBD6V7cl0H3hIRKQDFaVjsnRZnXN8qVN0jTmXUhh4SESkAxWlYzJ0Wp1zPPCpaE9mGJkm1OzHSURUHFWlYwFD7N/ptDrn6FKnqjXmDSvn49WnVvJJj4ioSKpKx+qWzMa5nluWVu10W51z9IlPxRpzJGig/qG52ryBRESlQFXp2DOPLMKOLbWIhYMwCjz96bo65+gTn4o15rFkWosCSCKiUrJ1bSV2H26Xeg0zOWXurAjqKuN488gFvH9uasuzgAEYhoH1K+ZpuTrn6BMf25MREblj3qwInlg5v+BTWj6Tk1PqKuP43hPVeOyhuUgkUxP2/lJpIGQAxy72440jF9DaNaDgJ1DH0cDH9mRERO55aUM1oqGg0L+dnJzS1NKJbXtbcPT8NSTTUwvcx5JpjCVSOHimB9v2tqCppVPizNVyNPCpWGMOGdCiAJKIqNSsXhrHji01iIWtXYcnJ6fcq8WefgI7MLHfpy7Bz9HAt3WtfOFiIg2k3Ww9QERUwhrqq6SSU2SH0Z7qdn/Z09HAJ7vGbPrRuxe0ePOIiEpRQ30VmhvrsXlVBSKhAKKTVuKioQAioQA2r6pAc2P9hIxMFcNo3WakHX58au0awLa9LRgZFy9iNwxg86oKLSb5EhGVsv6hMez7pBttV25hcHQc5dEwahbddzd7M1vf0Bgef/09qez8SCiAY9s3utrBxfFenauXxvHyk9X4wT+cE34NnSb5EhGVsrmzIkUPhlVRi63DMFqXxhIZCIn2vbn7Cpk3j4iInKGiFluHYbSuBL62q4NISA530uHNIyLyE6/UYrsS+Lzy5hER+YlXarFdCXxeefOIiPxEVb9Pt2uxXQl8XnnziIj8REUttg7DaB3J6uwbGsO+j7vRdnUQg6MJREIBJJJyG6Q6vHlERH5i1mIfOtMDkSwNXYbR2hr4WrsG8MaRCzjanrt7tyhd3jwiIr95aN5MoaAH6DOM1rbAl+nl1obRRO5ebjJJnbq8eUREftLU0om3jncK/VudhtHaEvjuNTCVW87MRac3j4jIL0R7dJr+4OtV2gyjVR74ZN+cfAwj86S3Y0uNNm8eEZFfyPToBIBLfcMKz0aO8sAn++YEjInLoNFQAGlk9vRe3FDNJz0iIof1DY3haPu1giOIpqNTm0mlgU/Fm2MYBrZ8pQJjidS0zVKJiMgZXunRaVIa+FS8Oel0GrfHk/jLrasZ7IiINOCVHp0mpYFPxZuTSgMftF/D119/Dxseno8Xn6jG6qVc3iRvmVzbWh4NoWZhOZ5fy9UN0o/X2kwqDXyq3pxUOlPzd/BMDz5o72NCC3nG0XO9+PMDZ3Hx2hDSwIRtgUjwCv7iH9uwoDyCJfEyVN4fYzAkLXitzaTSwKfqzTGl08DIeBK7DpwFAAY/KlmtXQP4/t+fwtlplnrGkpkoeOXmGK7cHMOJz28gGrqK3YfbufpBrsq0mbwqtaKnU5tJpb06VfTgzGVkPIVdB9pwqntA+WsT2a2ppRNbf3xs2qCXz2gilVn9+KwH2/a2oKmlU/0JEhXglR6dJqVRSsWbk89oIok3j1yw7fWJ7NDU0ok/+9lZjCfl5k+mkVn9eO2dz9D49gn0D42pOUGiIpg9Og3BVpO6tZk00mmZ4oOpGt8+gUNne6RKGvKJhAI4tn2jNm8e0XRauwawbW8LRsbF61qnM3/WDKxaPBuPPTSX+4BkO5nf54ABfGPFfG1+V5UHPju/7NFQAK9uWqlFHQhRIY1vnxDuYm9FKGAgGDC4D0i2k21HaTYkcft3Nbhz586dKl9w4ewo4rEQjnf0IyHTiTqHRCqN+bMiePqrC5W+LpFqfUNjeO2dz5R/B3JJpYFkKo2OvmHsP3kZ8ViIHY7IFnWVccRjYRzvuI6kwDNTIpXW4ndVeeAD5N+c6SSSKfzLRxahbIYjowSJhPzk+Odo6ehH0oHAly2RSuN4Rz/isTCDH9mirjKO9Svm4cbwHXTdGEE4YAjd4Ln5u6p8qTPbqe4BvHnkAt4/dw3jyZTUKCJTwADCwYDrj8pE03ml+VPsP3nZtePHwkE0N9Yz+JGt+ofGsO+Tbhy/2I8Pzl8Tusa78buqvvYgS11lHHsa1uHY9o1Yv3K+1PBZU3ZxO9O7SVeqmjmIYhY0OWHurAheWL8cM77cuxPhxu+qrYHPNHdWBP9l62qEg+oOl13czuBHunG73CCdvtcNn8hOssMJ3PhddSTwAfJ1IPmwuJ1009TSiVPdN90+jbvd8InspHJyg1McC3wA8NKGakRDQeWvy2Ud0kVr1wBee+cz20sYiqFTN3zyrlKc3OBo4Fu9NI4dW2oQC6s9LJd1SBcvNJ1QksSlii7d8Mm7SnFyg6OBD8g0mt6xpRaxcFDpsieXdchtr/30NK4O6nXzpUs3fPKuUpzc4HjgAzLBr7mxHptXVSASCijJ9uSyDrlp34ku/KTlc7dPYwKduuGTd6kYTuD076orgQ+YWOrw4LyZSl6TyzrkhqaWTvz7vzvl9mlMoVM3fPKuUpzc4FrgM82dFcEjS2YreS0u65DTmlo68ec/O6PVvh6gXzd88q5SnNygRd8vrw05JH9o7RrArgNtGE1oFvUARENBvLih2u3TIJ94aUM1fnG+T2g4QSQYQEV5FK80f4rB0QTKoyHULCy3dYqDrS3LitU3NIav/+Bd3JGYWcaRReS0xrdP4OCZHrdPY4pYOIAdW2rRUF/l9qmQj4hMbggYmcTEUDAw4cHH7ikOri91tnYN4E/+/p+kuthzWYecZnar0IlhZPoeMuiRG6xk7Jv/OZUGkl+2ocw2mkjZ2prS1aXOzB1CG0YTSanBtVzWIaft+7gbGiyW3DUjGMDGmvl4cUM1G1OTaxrqq1BXGb87nMBAJoiZoqEAEqk0Uul0Udf87NaU5uur4Frgkx1oaMos69Twy06Oars6KLU0r9rx73OZn5zXNzSGfR93o+3q4IT9uV2/9QiATG1125VbGBwdR3k0jPJYCM0fdVneFzdbU9ZVxpVc610JfGZSgEzQM4zMk96OLTVc1iHHuT19IVtZOMigR45q7RrAG0cu3F3un7g/dxW7D7ff3Z97Yf3yu/+t8e0TGEuKXffN1pR7GtbJnTxcCnxvHLmA0YT17B9TwAB+Y1UFl3XINaq6VaiwbE7M7VMgHym0RWUubR4804MP2vvuPpyonOIge6Pn+LdX9ocHgFAggF2/9Qjvcsk1NQvLETAua1G/t/krC90+BfIJK1tUk/fnhsbEH3ZMZmvK7KdIEY5ndaoYYREw2JeT3LV1bSUUT9gS9vuPVbl9CuQDoltU5v7c8Y4+baY42P7EN3nzs73nljY/PJGoebMi+LUV810vaVj7QJwrH+QImS2q0UQSZy4PKjkPFa0pbQt8021+qsC+nOS2P3pqJX5x/pqry53/6dmvuHdw8g0V+3P9w3eUnIuK1pS2LHU2tXRi294WHDrbg7EvCxFVY19OctvqpXE0fuMh147/vSceYnIXOULNFpWBoOT+gKrWlMoD373NT7mi9OmwLyfp4vvP1OIb1XMdP+436xZh+9O1jh+X/EnFlPVEKg3ZkKBqioPSwKeiPq8YHLdCOnn739bjGyucCX4BA/je+ofwP373UUeORwSoq1udO3OGFlMclAY+2fq8YrAvJ+no7e/W47f/2RJbj7Hx4fnY/+Lj2P4Mn/TIWarqVr+yeDaioaDQv1XZmlJZcouK+rxisC8n6eq//s4aVNwXwZ4POqSXdEwV90XwzCML8Ye/voI3e+QaVaPjHls+F0/VLrDcrlJ1a0plgU/F5mch7MtJutv+TC2W3B/Dn//s7ITmvFYYyHQm+s/PsUkD6WHr2krsPtwu9RrmFpX5O13MgAK7WlMqC3wqNj/zYV9OKiXZHerfbetFIlncpn7AAP7Fg3PwH56p5c0dacWcsn7obI/Qqt7kLapipjikkfk3drSmVDaI9rtvfYT32npVvNRddv/wRHbrHxrDvk+60do1gPaeW7g9nsTInSQSqRTSaQNl4SAWlEfwZM0C/P5jVXzCI221dg1g294WoSnrsXAQzY31Oa/h5ncke4pDzaL7JjwdqqYs8L3S/Cn2n7ws/TpL749hZcV9jvzwRERUPJFxcpktKr2GIytb6lS1+dlQ/4B0A1IiIlLPDF4y+3P5Zvg9v9a5hxxlT3x9Q2N4/PX3pAJfJBTAse0cqElEpLNT3QOW9+emn+GX+TfmDL/VS+3d1lIW+IDMkEGZzc/NqypyDhnU4Q6BiIgmKnZ/rtAMP5NTiYxKA5/qzU+d7hCIiMg6HfcFlQY+QN0PqdsdAhERWWNXJqgs5U2qG+qrsGNLLWLhYMGebIaR+eFyB73iGl1nT/ltaumUPn8iIlJDdobfm0cuKD6jDOVPfCaRzU9A3zsEIiIqns4Jj7YFPtPkzc9IKIDb40nEwgGMJdJTElXsSpAhIiIxIgmGe45exO7D7dIlbq9uWqm8xM32wGcqJlHlseVz8eGFPownxU+JJRFERGrIJBiqamry3Jol2P3tNdKvk01ZAft0CiWqmMugR85dkz6WAWDfJ90sgiciklDsdfvgmR580N43JcFQ1Qy/wdFxJa+TzfbAJ5LlKWM0kULblVuOHJvqgDsAABYVSURBVIuIyIusXLezEwyBe91dVM3wK4+GlbxONuVZndmcmsg+mR13CEREfiB63R4ZT2HXgTac6h4AYLaxlAsx0VAANYvuk3qNXGwNfE5MZM/FjjsEIiI/UFWCsHVtpfS5mDP8VLMt8Dk1kX0yu+4QiIi8Tva6nU4D75+7hv6hsbsz/ArVc+czeYafSrbt8TkxkT2XXHcI7PVJRFSYiut2doLhSxuq8YvzfUJ12dFQEC9uqJY+n1xsC3x2TmTPZ/IdwvSpuFex+3A7e30SEX1JxXU7O8Fw9dI4dmypEWxjWWNbMxLbAp+qVFYrsu8QZFNxiYj8xo4SBBUz/FSzLfCpSmUtVvYdgopUXCIiv7GrBKGhvgp1lXGhNpZ2sC06qZjIXozJdwiyqbh1lXH2+iQiX1Jx3c6XYFhXGceehnVFz/Czk20ty1Q0KA0HDXyjeh4+vNhf9B0Ce30SEYnRubG0SrY98ZmprDJB6MmaBZbuEFSm4ur8oRER2UHFdduuEgSVbN2IU5XKOndWpKjem6pTcYmI/EbXEgSVbO3cYqayxsLWDiOayqo6FZeIyG9WL43j5SerEQpYqzy3uwRBJdtTL0VTWZ/+6iLsOXrRUtG5zt3AiYh0l137XGz6h1MlCCo5UnNgJZX1qdoKHDzTgz/7Waa8wErRuc7dwImIdFao9nmyUMBAMGA4VoKgkmPFdsWksv789BX86U8/Ey46tzMVl4jIq8TGx6XxR0+txAtP6L+nN5ljE9gLEXnjM2vKtXeDn19ScYmIVGntGsC2vS1CySyxcBDNjfUl9bQH2JzcUixV85907gZORKQjVWOISokWgU/lG//ShmpEQ0Gh1yqVVFwiIhVU1j6XEtcDn+o33ukSCiKiUqWy9rmUONtJOgc7is517AZORKQbVbXPrV8MWC4/c5Prgc+uonPduoETEelGVe3zP5y5infP9ZbMzFPXA5+dRec6dQMnItKNqtrnVBpTHmB0nnnqeuBzoui82F6fRER+4sT4OB1nnrqe3JJ54+VOg0XnRETWbV1b6dixJpefucn1wKfijU8D2Pqocx8gEZEXyNY+W6VL3Z/rgY9F50RE7pGpfbZKl7o/1wMfIPfGGwA21VaoPSEiIp8QrX0WpUPdnxaBT+aNT6eB//jTz9DU0qn+xIiIfKChvgo7ttQiFg7avuypw8xTLQIfMPGNtyKNexlDDH5ERGIa6qvQ3FiPzasqEAkFEJ2UdBgNBZQFRbdnnmozncH0tx934Y//9hRSAmdVqp3CiYh0kq/2+WTXAH5++qr06z+3Zgl2f3uNgjMV43od32T/eKYHopHYzBja07BO6TkREflJvtrnPUcv4r223pKfearNUifg307hRESlwCvlZ1o98dnRsJqIyM/6hsaw7+NuJQ2kzfKzQ2d7hB5QdCk/0yrw2dWwmojIb1q7BvDGkQs42n4NAJQ1kH5pQzV+cb5PaGK7LjNPtQp8djas1oXKuy8iolyaWjqnHcsm00DaLD/bdeAsRsaLf1DRaeapVoFPZcNq3QKMXXdfRETZMkGvuKAk2kC61GeealXOsOfoRew+3C613DkjaKBq7kx8fv02gMkBJjODz+kAU+juy6TjLwgRlY7WrgFs29sitAxZbDlY9kNF940R/GpgBL23xhAKGDmvtzrOPNUq8PUNjeHx19+T3uczgGlLIgoFGJVPi1buvkyZJYFaBj8isqTx7RNSiSebV1XkLQebbtUqEjSQSKWxoDyKyngMlfeXaT3zVKulTtmMIVOhf5rv8V71cmRr1wB2HWizFPSAe+M76irjWt0lEZG+VJaDTQ5WhVatxpKZP7w6OIqB2+P4zTWLtb5x16qOD3C2U3j2fKimlk5s29uCQ2d7MJZI5ZwmPJZI4eCZHmzb21JUe7Q3jlzAaML6kkPmeHqM7yCi0qCyHCzbvVWr6bdqgIkPFTq3kNQu8DndKXw0kcT3/+6U8g+WxfhE5CQ7ysFkV610GDqbi3aBD3C2U3g6DZy5ckv5B2vX3RcRUS52lIN5ddVKy8AHFNcpPBIKYOWCWZgRdGh88CTTfbAsxiciJ6ksBwO8vWqlVXLLZHWVcexpWJe3U/jWRyvxZz87g/beIVfOb7rNYD8U4xORNXbWF9csLEckdFVZA2kvt5DUOvCZ8nUKB9QFGFH5PljVd19EVLqcaGCxdW0ldh9ulzrP7AbSXl610naps1iqAoyofB9s5u5L7u3VYXwHEcmxI2M8F7McTDQvYnIDaS+vWpV84FMRYGTl+mC9Mr6DiMQ5XQogUw42uYG0l1etSj7wqQgwsnJ9sKrvvoiotLhRCiBaDpargbSXV61KPvDJBhhZ032wKu++iKi0uFUKYKUczDAyPTpztUj08qpVyQc+wNluL5NN98GqvPsiotLhdilAoXKwgJH534r5s/A///XanO3FvLxqFdy5c+dOt09C1sLZUcRjIRzv6EciVfxvWiwcwIqKWegfviN0XMMAnqpdgN9Ztyzv36mrjCMeC+N4x3UkC3wLprv7IqLS8ZPjn6Olox9JC9ejycIBA7PLwlj3wByhf19RHsWzdYuxunI2Wrtv4sbtOzCMzM26+b/hsQTeab2M05dvYtn9ZVg4OzrhNZbNKcP+k5ctXVdNsXAQP/xWHSrKo4X/ssM88cQHiD/e/+C5OtuXI4stxt+8qgLNjfUMekQlTpdSgKaWTrzQ9AnOXxtCKg1Mjl+FMkq9umpVEnV8xWqor0JdZRxvHrmA989dg4F7k4aB/POhZKYJL47HsOfoxYIFqcUU4+u4JEBE1ulQCqBqIG2pD53NRat5fCpZDTBWh8V+57EH0NE3nKcg1Z2Bt0Skh1eaP8X+k5elX+e5NUuw+9trcv636brAdN8YUT6Q9lT3gOWHCl15NvCJKPaDfXDuTPyv45975u6HiNTac/Qidh9ul24f9uqmlVO6Qk3fBSZznZodC+ParbGCs0lzKTSQ1gurVr4NfNPdLQHI+8H+/PQVrSeq29kLkIiK0zc0hsdff08q8EVCARzbvnHC97bYlSlZuY7tJb4LfMXcLeVbomztGlC+fKCKzM9FROp952/+393vo1W5nrqs7NnJyve06RWeyeoshmzPPF1nUznVC5CICmvtGkDj2ydw7GKf8GtMzhgX7QIjStfm0qp4KqtzOrIZTioLUlUuH6jK3CIieSqWInOVAsjcdIvSsbm0Kr544lPRM0/Hiepu9AIkotysNKTOJV8DC9mbblE6NpdWxReBT8USpS4Fqdl0XXol8hvZpchw0MjbwELFTbdVujaXVsXzgU/VEmXfkFhbs8lULR+43QuQiO6RXYr8tep52NOwLmfym4qbbqt0bS6tiucDn6olyhvDagKEquUDHZdeifxIxVLksYv9eW9CVXWBKZbOzaVV8XzgU7VECcPQajaVjkuvRH5k902oqoGwxfLDSDTPBz5Vd0tzymZIv4bK5QMdegESkf03oSoGwhZL9+bSqng+8Km6W1Ix8HbOzDD++G9P4ZXmT7Hn6EWp/TVVP5eXM7eInGD3TaiKgbCF+G0kmufr+DJ3S1ele+bVLLoP9Q/OxS/O9wl1bgGAKzfHcOVm75eveRW7D7cLd1NR+XMRkTi7b0LNm+5DZ3uE9xEr7otgYGS85JtLq+L5wLd1bSV2H26Xeg1ziXLurIjQCKNczF++g2d68EF7n+VG1ip/LiIS58RN6EsbqoVvumPhIPb+/josicdKvrm0Kp4PfLJ3S5MznKzMpiqGaDcV1T8XEYlx4ibUHAgrOjfUfJLzau9Nq4I7d+7c6fZJ2G3ZnDLsP3kZicnjh4sQCwfxw2/VoaI8evfP6irjWL9iHm4M30HXjRGEA4bQa2dLpNI43nEd61fMm3Cs6cj8XKGAgUXxGP7Pqct4/1wvOvtv48F5M1E2w/P3QkRKlc0I4Z9+dRMdfcPCr7F+xTz87tcemPbv1FXGEY+FcbzjOpIF7nb9tmdnlW+mM4h0Ni9mnNDk2VRnrgziys1RoXMsNAcrF9GO7aFJwZoTHIgKyzf2a9WicrzQ9LHw/n84aGBjzYKivnteGgjrFt8EPsD6lHWr+252zeAqROWMLg7PJZqqmLFfD82fiY7eIYwlxb6EVr97XhgI6xZfBT7A3rslO6cuFzLdzxUygITFT9nJ4blEOrNywxwKGEingWQ6LTmdgd89O/ku8JnsuFt6pflT7D95WfrcnluzBLu/vUbo307+uZKpNP7vhT7h/U07h+cS6U5kKyESCmD5/Jk43zuEccGnP3737OXbTIa5syLKM5zsLmTNt7/w/Np7wXryz9X49omCG+H5mBMcrOw5kjrFfN5ePr7bRCcujCVSuNR3G48smY1PvhAb/cXvnr18G/jsYFch6/T7C/kL4XUdnuu0UruAi37eXjm+LqTGfo0ncbJLfN6lV757umLgU8iOQtZC+wvTFcKrbJ5bivU/pXgBl/m8vXB8XUjfNALyiWYo3e+e7jzfq9NJKnrqZReyWpnonF0I39TSCcDfExyaWjqxbW8LDp3twVgiNeV9GP3yzw6e6cG2vS133zM3yX7epX58nbgx/HWyUv3ulQIGPoVkG1lnd1MR3V8YGU9h14E2nOoe8O0Eh1K8gKv4vEv5+LpxY/hrLqX23SsVDHyKvbShGtFQUOjfZs/Bktpf+HJjXNWe45krg2iV2K9wUqlewFV83qV8fN04Pfw1H05PsQcDn2JmT71Y2Npbm91TT1VSyrI5ZUrmeF25OarNcmAhpXgBV5mEVIrHd1rf0Bj2HL2IV5o/xXff+ijnmDCnh7/mwukp9nH/0/UgK42sc3VrUJWUopJII22nlWoWq9tJSG4f36msWyvJTioS1WRxeop9GPhs0lBfhbrKuFCXGFVJKV3XR6TneGUzlwPrKuNaFta6fQEX5XYSklvHdzLr1mq26stPVksdDwACBiDau57TU+zFwGejuso49jSss9wlRmVSyr/buEJqeO5khQpr3ayZczuAiHI7CcmN4ztZNmGl+4qZ7PSjd8/jofkz0Xb1lvDYr689OAetXTeFvnvZ+/2kHgOfA6x2iVFZCC86xyuffMuBOtTMuR1ARNk9wVu344sEItFldplkp47eYcwIBoRupqKhIP7kmVqc6h6QnqFH6jG5RUOZ/QW5jyZ7Y7yhvgo7ttQiFhbLNp3MXA406VIz53YAEaX689b5+E5n3cokO91JpbB8/kypRLXs716hMifO0HMOA5+GVBfCA5ng19xYj0WzixtyO53s5UCdauaW3l+GoGRWjxuZdHZ83roe38msWxXJThevDePlJ1dIBS7zu7d5VQUioQCik24yoqEAIqEANq+qQHNjPYOeA7jUqSGzEF40KSXfxnhdZRy1i8qFB+VmGxwdl757V5UkYy6zHjl3DYLN8O9SlUlnZa/Trs+7WE4dX0UgOnS2Fxd6bqG6ovDNiapkJ8Mw0NxYLzXOTHS/n+zBwKeplzZUCyelTLcxrnI5UMXdu2z3edVDeGUz6UT3Ou36vIvlxPFVBKJkKo3NP/oAT62qKLhfrDLZ6YX1y5UELjumwpB1DHyaEk1KKbQxrqqR9tI5Mfz4gw5Xa+ZEZqVNRzaAyGQq2vV5F8uJ46tqA5ZMF5ftaUeyEwOXNzDwaUy2ED6XrWsrsftwu9R5qZpcbCbJfOvRSsslEKLLrPnIBhAVmYp2fN5W2H18lW3Aisn2LNVkJ7JfcOfOnTvdPgnKr64yjvUr5uHG8B103RhBOGBMmKYeDQUQDBh4qnYBfvitOmxatXDa1yubEcI//eomOvqGhc7HMICnahdg+E4Sn10eFHoNUyKVxsVrQ3jj/Qto6ejHZ5cHcalvGG1Xb+FE53X81YeXcPryTSy7vwwLJyXlvPbOabT3ytfbqcika+0awMvNJy0H4UQqjeMd17F+xTxUlGd+PtWft1Xm8a/eHEXXjREYmHijEwkFEBI8/vvnetF2VW2NZK730NTZfxsfdV5HUrSKHJn3+5urF2PdA3NkT5U0YqTTKnp6kBNUbYy3dg1g294Wof2cWDiI5sZ6/Ld3z+O9tl7L/96qXE8WfUNjePz196SXzWYEDWysWZA3IaFYjW+fkEoM2byqIudepxuJENl7lOl0GneysoUCRuYpff3K+XjlyZWW6zH3HL2I3YfblbcBy/ceqvg9iYQCOLZ9IxNPPIZLnSVE1f6Civ0cp5r45lrSUpEkEQoY+N4Ty/HqpoelXsfO/qDm552dIfrLS9dx9sqgLd1wCu1Rmg9OR9qvoaXjuuVlVhXL7Lnkew/dzpYlfTHw+ZTsfo7TTXyzSyBUJEkkUml8cX3k7v8XbbVmZ39Q53tZ2ttNRTYQTSffe+h2tizpiXt8Piazn1Q1byb++sNLUvsnViXTadwYvoPb4ylcEtyjzLYkHkPV3Jl47Z3TeO2dzyzvMwJA0y8/V7LXOX9WBE9/9d7729TSiZebT6K99xYSqfSU99n8s46+Yew/eRnxWEh4uVblHmUhy+aUYf/JyxN+z1TI9R4CwMLZUcRjIRzv6Ld0zMzqRq3yPVTSAwOfz1WUR/Fs3WL83teWYXZZGPNnRbAkHsOayji+uXox/vL51fiddcumXNhkk2REdd0YwYoFM3GhV/645dEQfvxBh1Rw+d8fdysLwr+5ZgkA62UamQDUj3gsLBT8ZBKFzJuRZ+sWF/X3RQNRMbLfw2x1lXHEY2Ec77iOZIFHTbYN8wcudRIAsf1DmWUkUQYyy56RkFjzYFPIAD67PFjUxXe6pT3VKfNOd8NxY4ahlWV2K6YrO5AZE0bew8BHwlRPfijGaCKFMgXNthNpwOoVN1dwUdUQwOwP6nQ3HLdmGGYHokNne6WXzIvpscq2YWRi4CMpdt29T2cskbItSaKQycFFVUOArY9WuvL05eYMQzMQne+5had/9IFUn1UrPVbZfYU4nYGkFdt9ftFsNXfT5dEwXtpQjWhIzZglK7KDC3AvU7FQ5/58slPmVT59FUuHGYYrKu7Dk7UVSt5DomIw8JES5t37se0b8eqmlXhuzRI8WbMAz61Zglc3rcSx7RvxncceVDb3zVxmtTorLRTI1PDJmBxcZIJwdsq8G09furT1UvUeEhWDS52k1HTLSCqXBQGxWsSVFbPQ2n1T6hwmBxdVDZ7dePpSvUcpyu0m3eQvfOIjx6hcFjRZHfKpajlscnBRMWnbjacvt4fgZuO0cnIKn/jIUXZ00rCSrWdncJFNmXfj6Uu3tl4sOyAnsEk1OU5kjp7ZSUP27l5Fo+RoKIBXN62cNjNQJGXerabKKpqW2xGAWHZAdmHgI1cUOzld9dw53Tv22zXpoRA3b0aInMY9PnKF1b05VRdXO/YZVXIru5H7a+QnfOIj1zm9pKXr0p7JzaevU90D3F8jz2PgI1/SfWnPraVgE/fXyMsY+Mi33A4uhfDpi8geDHzka6UQXPj0RaQWAx8RGFyI/ISBj4iIfIXlDERE5CsMfERE5CsMfERE5CsMfERE5CsMfERE5CsMfERE5CsMfERE5CsMfERE5CsMfERE5Cv/HyzJuy0X9n6DAAAAAElFTkSuQmCC\n",
            "text/plain": [
              "<Figure size 432x288 with 1 Axes>"
            ]
          },
          "metadata": {
            "tags": []
          }
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "_5jUXeKhIrCB",
        "colab_type": "text"
      },
      "source": [
        "### Formulating the problem\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "JnFcCgU3bqIg",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "N = 30\n",
        "k = 6 # number of targets\n",
        "\n",
        "subconstellation_size = N // k  # satellites per constellation"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "WyJQnYPTc3Hp",
        "colab_type": "code",
        "outputId": "e8566e4f-d284-4092-f708-9e7a6849e9e7",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 54
        }
      },
      "source": [
        "coverage = {}\n",
        "for i in range(N):\n",
        "  np.random.seed(i**2)\n",
        "  coverage[i] = np.random.randint(0, 100)/100\n",
        "print(coverage)\n",
        "\n",
        "score_threshold = 0.4"
      ],
      "execution_count": 79,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "{0: 0.44, 1: 0.37, 2: 0.46, 3: 0.92, 4: 0.41, 5: 0.04, 6: 0.05, 7: 0.42, 8: 0.68, 9: 0.67, 10: 0.08, 11: 0.66, 12: 0.6, 13: 0.35, 14: 0.28, 15: 0.35, 16: 0.32, 17: 0.47, 18: 0.25, 19: 0.83, 20: 0.92, 21: 0.13, 22: 0.31, 23: 0.09, 24: 0.19, 25: 0.51, 26: 0.52, 27: 0.22, 28: 0.21, 29: 0.36}\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8KBpXzrwgN3f",
        "colab_type": "code",
        "outputId": "51fa9687-0016-42c6-e4b9-25e34c447e2a",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 279
        }
      },
      "source": [
        "lists = sorted(coverage.items()) # sorted by key, return a list of tuples\n",
        "x, y = zip(*lists) # unpack a list of pairs into two tuples\n",
        "plt.xlabel(\"Satellite #\")\n",
        "plt.ylabel(\"Coverage\")\n",
        "plt.hlines(score_threshold, 0, N, linestyles='dashed', colors='r')\n",
        "plt.bar(x, y, align='edge')\n",
        "plt.show()"
      ],
      "execution_count": 80,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYIAAAEGCAYAAABo25JHAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+j8jraAAAVhElEQVR4nO3df5QdZZ3n8ffHAAKKoCa6LgGDiijruhEjDuooDuIC8kOPkYEVx7hqGJU5MiouosMizqKj6+gZBRRXD46ORkYdJ2qU8Qeo61EgIKgBwcjiEmQgIOq4CIp+949b0U53J30Tum7n5nm/zunTt37cut/qut2ffp6qem6qCklSu+4z1wVIkuaWQSBJjTMIJKlxBoEkNc4gkKTG7TDXBWyp+fPn16JFi+a6DEkaK5dffvltVbVgumVjFwSLFi1i9erVc12GJI2VJD/e1DK7hiSpcQaBJDXOIJCkxhkEktQ4g0CSGmcQSFLjDAJJapxBIEmNMwgkqXFjd2fxuFp06uc3u/yGtz1nRJVIM/P92hZbBJLUOINAkhpnEEhS4wwCSWqcQSBJjTMIJKlxBoEkNc4gkKTGGQSS1DiDQJIaZxBIUuMMAklqnEEgSY0zCCSpcQaBJDXOIJCkxhkEktQ4g0CSGmcQSFLj/MxiqSF+FrGmY4tAkhpnEEhS4wwCSWpcr0GQ5LAk1yZZm+TUaZbvneSiJN9J8t0kR/RZjyRpqt6CIMk84GzgcGB/4Pgk+09a7U3ABVX1BOA44Jy+6pEkTa/PFsGBwNqqur6qfg2sAI6ZtE4BD+ge7w78pMd6JEnT6DMI9gRunDC9rps30RnACUnWAauAv5huQ0mWJ1mdZPX69ev7qFWSmjXXJ4uPB86vqoXAEcBHkkypqarOq6olVbVkwYIFIy9SkrZnfQbBTcBeE6YXdvMmeilwAUBVfQvYGZjfY02SpEn6DILLgH2T7JNkJwYng1dOWuf/AocAJHksgyCw70eSRqi3IKiqe4CTgAuBaxhcHbQmyZlJju5Wey3w8iRXAR8HllVV9VWTJGmqXscaqqpVDE4CT5x3+oTHVwNP7bMGSdLmzfXJYknSHDMIJKlxBoEkNc4gkKTGGQSS1DiDQJIaZxBIUuMMAklqnEEgSY0zCCSpcQaBJDXOIJCkxhkEktQ4g0CSGmcQSFLjDAJJapxBIEmNMwgkqXEGgSQ1ziCQpMYZBJLUuB3mugCNl0Wnfn7GdW5423NGUImk2WKLQJIaZ4tAvZmp9WDLQdo22CKQpMbZItDYsIUh9cMWgSQ1ziCQpMYZBJLUOINAkhpnEEhS4wwCSWqcQSBJjTMIJKlxBoEkNc4gkKTG9RoESQ5Lcm2StUlO3cQ6xya5OsmaJB/rsx5J0lS9jTWUZB5wNnAosA64LMnKqrp6wjr7Am8AnlpVdyR5SF/1SJKm12eL4EBgbVVdX1W/BlYAx0xa5+XA2VV1B0BV3dpjPZKkafQ5+uiewI0TptcBT560zqMBknwTmAecUVVfnLyhJMuB5QB77713L8Vq++EopdKWmeuTxTsA+wIHA8cDH0iyx+SVquq8qlpSVUsWLFgw4hIlafvWZxDcBOw1YXphN2+idcDKqvpNVf0f4DoGwSBJGpE+g+AyYN8k+yTZCTgOWDlpnc8waA2QZD6DrqLre6xJkjRJb0FQVfcAJwEXAtcAF1TVmiRnJjm6W+1C4PYkVwMXAadU1e191SRJmmqLThYn2bWq7hx2/apaBayaNO/0CY8LeE33JUmaA0O1CJI8pfuv/Qfd9H9Kck6vlUmSRmLYrqF3Af8ZuB2gqq4Cnt5XUZKk0Rn6HEFV3Thp1m9nuRZJ0hwY9hzBjUmeAlSSHYFXMzgBLEkac8O2CP4ceBWDu4VvAhZ305KkMTdUi6CqbgNe2HMtkqQ5MFQQJPm7aWb/HFhdVf88uyVJkkZp2K6hnRl0B/2w+3o8gyEjXprk3T3VJkkagWFPFj+ewWcG/BYgybnAN4CnAd/rqTZJ0ggM2yJ4IHD/CdP3Ax7UBcPds16VJGlkhm0RvB24MsnFQBjcTHZWkvsBX+6pNknSCAx71dAHk6xi8KljAKdV1U+6x6f0UpkkaSS2ZNC5u4CbGZw4flSSR1XV1/spS5JGq+VPthv28tGXMbibeCFwJfBHwLeAP+mvNEnSKAzbIng18CTg21X1zCSPAc7qryxJmh0t/6c/rGGvGrqrqu4CSHLfqvoBsF9/ZUmSRmXYFsG67kPlPwN8KckdwI/7K0uSNCrDXjX0vO7hGUkuAnYHvthbVZKkkZkxCJLMA9ZU1WMAquprvVclSRqZGc8RdHcPX5tk7xHUI0kasWHPETwQWJPkUuD/bZhZVUf3UpUkaWSGDYK/6rUKSdKcGfZk8deSPBzYt6q+nGRXYF6/pUmSRmHYO4tfDiwHHgQ8ksFHVr4POKS/0iR5M5RGYdgbyl4FPBX4BUBV/RB4SF9FSZJGZ9hzBHdX1a+TAJBkB6B6q2qM+B+bpHE3bIvga0lOA3ZJcijwj8Bn+ytLkjQqwwbBqcB6Bh9LeSKwCnhTX0VJkkZn2K6h5wJ/X1Uf6LMYSdLoDdsiOAq4LslHkhzZnSOQJG0Hhr2P4CVJdgQOB44Hzk7ypap6Wa/VzTJP7ErSVEP/Z19Vv0nyBQZXC+3CoLtorIJAkjTVUF1DSQ5Pcj7wQ+D5wP8C/l2PdUmSRmTYFsGfAZ8ATqyqu3usR5I0YsOeIzg+yUOBQ7ubyi6tqlt7rUwj5fkTqV3Ddg29ALgUeAFwLHBJkqV9FiZJGo1hLx99E/CkqnpxVf0ZcCBDDE2d5LAk1yZZm+TUzaz3/CSVZMmQ9UiSZsmw5wjuM6kr6HZmCJHuIy7PBg4F1gGXJVlZVVdPWm834NXAJUNXvR2zi0bSqA0bBF9MciHw8W76TxkMM7E5BwJrq+p6gCQrgGOAqyet9xbgb4BThqxlq6342NRGyece88d89IDnsPNv7oKDD576pGXLBl+33QZLp/aGHbn7k/ncY5/Ow36xnnd97p1Tn//U38FRR/GI29dx1oXvnbL4PU85jm8uWgxXXgknn8yK62/faPnbn/5irlj4WA5Ydw2v//qH4dvv2HgD7343LF4MX/4y/PVfT339978f9tsPPvtZeOc09X3kI7DXXhx5zdc54TtTD+krnvsG7th1dzj/fDj//Cn1LXvBGdy1486ccMXnOfIH3xjM7Gpccf3tHPdf3gbAyy/5NIf86NKNN37Ve+ELXxg8fstb4Ctf2Xj5gx8Mn/rU4PEb3sCKj31uo8U37zafvzzqdQCc/uXz4OA/vC7A9Q/ak9MO+wsAzvrie3jET2/aqD4WLx78/ABOOAHWrdv49Q86CN761sHj5z8fbt943znkEPirrmF8+OHwq19tvPzII+F1g/qmfW8deyy88pVw551wxBFTly9bBizggXf+nHM/89Ypiz/6hCOA58CNN8KLXjT1+a99LRx1FFx7LZx4IsBGx2/De2//W67n9K+cN5g54dhNee9N9O13zNp7j098As49d+ryT34S5s///XtvilWrYNdd4Zxz4IILpi6/+GJg+vfeXTvcl2XHvnkw0b33Jv5s7tjlAbzieacB8Pqvnc8BN/1g49+9hQvhox8dPD755MHv70SPfjSc1/1Mly+H667bePnWvve6fZptM/1X/6gkT62qU4D3A4/vvr4FnDfDtvcEbpwwva6bN3H7BwB7VdVm/w1OsjzJ6iSr169fP8PLSpK2RKo2PZp0ks8Bb6iq702a/x+Bs6rqqM08dylw2Ia7j5O8CHhyVZ3UTd8H+CqwrKpuSHIx8LqqWr25gpcsWVKrV292lU3qo9tl2G3O9nqzbbbq25J1t3RftvWfYR/8Gd57Le7zdJJcXlXTnoed6WTxQyeHAEA3b9EMz70J2GvC9MJu3ga7AY8DLk5yA/BHwEpPGEvSaM0UBHtsZtkuMzz3MmDfJPsk2Qk4Dli5YWFV/byq5lfVoqpaBHwbOHqmFoEkaXbNFASru88r3kiSlwGXb+6JVXUPcBJwIXANcEFVrUlyZpKjt7ZgSdLsmumqoZOBf0ryQv7wh38JsBPwvJk2XlWrmHR1UVWdvol1D55pe5Kk2bfZIKiqW4CnJHkmg/58gM9X1Vd7r0ySNBLDjjV0EXBRz7VsM7bkyhhJGnfDDjEhSdpO+ZGTkjTH5voeBlsEktQ4WwRq1qjv2t2abUqjYItAkhpnEEhS4wwCSWqcQSBJjTMIJKlxBoEkNc7LR6U5MNc3EEkT2SKQpMbZIpDUO2+227bZIpCkxhkEktQ4g0CSGmcQSFLjDAJJapxBIEmN8/JRaQbe/KXtnS0CSWqcQSBJjTMIJKlxBoEkNc4gkKTGGQSS1DgvH5W2A17iqnvDFoEkNc4gkKTGGQSS1DiDQJIaZxBIUuO8akiStsD2eIWWLQJJalyvQZDksCTXJlmb5NRplr8mydVJvpvkK0ke3mc9kqSpeusaSjIPOBs4FFgHXJZkZVVdPWG17wBLqurOJK8A3g78aV81SdKojFMXUp8tggOBtVV1fVX9GlgBHDNxhaq6qKru7Ca/DSzssR5J0jT6DII9gRsnTK/r5m3KS4EvTLcgyfIkq5OsXr9+/SyWKEnaJk4WJzkBWAK8Y7rlVXVeVS2pqiULFiwYbXGStJ3r8/LRm4C9Jkwv7OZtJMmzgDcCz6iqu3usR9J2ZJz64Ld1fbYILgP2TbJPkp2A44CVE1dI8gTg/cDRVXVrj7VIkjahtyCoqnuAk4ALgWuAC6pqTZIzkxzdrfYO4P7APya5MsnKTWxOktSTXu8srqpVwKpJ806f8PhZfb6+JGlm28TJYknS3DEIJKlxBoEkNc4gkKTGGQSS1DiDQJIaZxBIUuMMAklqnEEgSY0zCCSpcX54vaSt5gig2wdbBJLUOINAkhpnEEhS4wwCSWqcQSBJjTMIJKlxBoEkNc4gkKTGeUOZpG2KN6mNni0CSWqcLQLNOf8DlOaWLQJJapxBIEmNMwgkqXEGgSQ1ziCQpMYZBJLUOC8f3c55aaakmdgikKTG2SIYU/6nL2m22CKQpMYZBJLUOINAkhpnEEhS4wwCSWpcr0GQ5LAk1yZZm+TUaZbfN8knuuWXJFnUZz2SpKl6C4Ik84CzgcOB/YHjk+w/abWXAndU1aOAdwF/01c9kqTp9dkiOBBYW1XXV9WvgRXAMZPWOQb4cPf4k8AhSdJjTZKkSVJV/Ww4WQocVlUv66ZfBDy5qk6asM73u3XWddM/6ta5bdK2lgPLu8n9gGu3sqz5wG0zrjUe3Jdtz/ayH+C+bKvuzb48vKoWTLdgLO4srqrzgPPu7XaSrK6qJbNQ0pxzX7Y928t+gPuyreprX/rsGroJ2GvC9MJu3rTrJNkB2B24vceaJEmT9BkElwH7JtknyU7AccDKSeusBF7cPV4KfLX66quSJE2rt66hqronyUnAhcA84ENVtSbJmcDqqloJfBD4SJK1wE8ZhEWf7nX30jbEfdn2bC/7Ae7LtqqXfentZLEkaTx4Z7EkNc4gkKTGNRMEMw13MU6S3JDke0muTLJ6ruvZEkk+lOTW7h6SDfMelORLSX7YfX/gXNY4jE3sxxlJbuqOy5VJjpjLGoeVZK8kFyW5OsmaJK/u5o/VcdnMfozdcUmyc5JLk1zV7cubu/n7dMPxrO2G59lpVl6vhXME3XAX1wGHAusYXNF0fFVdPaeFbaUkNwBLJt94Nw6SPB34JfD3VfW4bt7bgZ9W1du6kH5gVf23uaxzJpvYjzOAX1bV/5zL2rZUkocBD6uqK5LsBlwOPBdYxhgdl83sx7GM2XHpRli4X1X9MsmOwP8GXg28Bvh0Va1I8j7gqqo6996+XistgmGGu9AIVNXXGVwhNtHEoUY+zOCXd5u2if0YS1V1c1Vd0T3+N+AaYE/G7LhsZj/GTg38spvcsfsq4E8YDMcDs3hMWgmCPYEbJ0yvY0zfIJ0C/iXJ5d3wG+PuoVV1c/f4X4GHzmUx99JJSb7bdR1t010p0+lGAH4CcAljfFwm7QeM4XFJMi/JlcCtwJeAHwE/q6p7ulVm7e9YK0GwvXlaVR3AYGTXV3XdFNuF7obCce2vPBd4JLAYuBl459yWs2WS3B/4FHByVf1i4rJxOi7T7MdYHpeq+m1VLWYwKsOBwGP6eq1WgmCY4S7GRlXd1H2/FfgnBm+ScXZL17+7oZ/31jmuZ6tU1S3dL+/vgA8wRsel64f+FPAPVfXpbvbYHZfp9mOcjwtAVf0MuAg4CNijG44HZvHvWCtBMMxwF2Mhyf26E2EkuR/wbOD7m3/WNm/iUCMvBv55DmvZahv+aHaex5gcl+7E5AeBa6rqbycsGqvjsqn9GMfjkmRBkj26x7swuNDlGgaBsLRbbdaOSRNXDQF0l4y9mz8Md/E/5rikrZLkEQxaATAYIuRj47QvST4OHMxgON1bgP8OfAa4ANgb+DFwbFVt0ydiN7EfBzPofijgBuDECX3s26wkTwO+AXwP+F03+zQG/etjc1w2sx/HM2bHJcnjGZwMnsfgH/YLqurM7vd/BfAg4DvACVV1971+vVaCQJI0vVa6hiRJm2AQSFLjDAJJapxBIEmNMwgkqXEGgZqQ5I3dKI7f7UagfPIM6y9L8u+H2O75SZZ2jy9OsqR7vCrJHt3XK+9F3ScmeUmSxUnev7XbkTbHINB2L8lBwJHAAVX1eOBZbDz21HSWATMGwaZU1RHdHaF7AFsdBMAfA18HntF9l2adQaAWPAy4bcONN1V1W1X9BCDJ6UkuS/L9JOdlYCmwBPiHrvWwS5InJvlaN9DfhZPuVp0ig8+MmA+8DXhkt513dMtO6V7zuxvGmZ/m+X/ZDTj2PAZDJrwZeGM39LA0qwwCteBfgL2SXJfknCTPmLDsvVX1pO4zBXYBjqyqTwKrgRd2g37dA7wHWFpVTwQ+BAx7N/epwI+qanFVnZLk2cC+DMa7WQw8cbpBA6vqXQyGFfhqV8N1VbV/Vf351vwApM3ZYeZVpPHWfbjHExl0szwT+ESSU6vqfOCZSV4P7Mrgtv01wGcnbWI/4HHAlwbD2TCPwSiWW+PZ3dd3uun7MwiG6bp9DgCuSvIA4Gdb+XrSjAwCNaGqfgtcDFyc5HvAi5OsAM5h8GlvN3afMLbzNE8PsKaqDpqFUgK8tao2eeI3yUMYtGIeAtzFYJDE3bquoudX1Y9moQ7p9+wa0nYvyX5J9p0wazGDQdQ2/NG/rRvDfumEdf4N2K17fC2woDvpTJIdk/yHIV9+4nYALgT+a/d6JNmz+8P/e1V1a9cddAWDLqSPAi/pupcMAc06WwRqwf2B93TD+t4DrAWWV9XPknyAwbDE/8pguPINzgfel+RXDMaBXwr8XZLdGfzevJtBN9JmVdXtSb6ZwYfcf6E7T/BY4FtdN9MvgROYNNZ/Bp+z/eCqui3JU4C/nbxtabY4+qgkNc6uIUlqnEEgSY0zCCSpcQaBJDXOIJCkxhkEktQ4g0CSGvf/ARTBrE40h5cSAAAAAElFTkSuQmCC\n",
            "text/plain": [
              "<Figure size 432x288 with 1 Axes>"
            ]
          },
          "metadata": {
            "tags": [],
            "needs_background": "light"
          }
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "HuF1phUuCkvG",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        },
        "outputId": "95dddcf5-54c2-4047-f80a-1a6e9bceeb62"
      },
      "source": [
        "import math\n",
        "\n",
        "def nCr(n,r):\n",
        "    f = math.factorial\n",
        "    return f(n) / f(r) / f(n-r)\n",
        "\n",
        "print('# possible subconstellations: ', nCr(30,5))"
      ],
      "execution_count": 100,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "# possible subconstellations:  142506.0\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ojJpAl7h_7VC",
        "colab_type": "code",
        "outputId": "c5adfea3-1986-4a1d-8a77-ddb07d4de11e",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "subconstellations = {} # create dict of subconstellations and its coverage\n",
        "\n",
        "for subconstellation in itertools.combinations(range(N), N//k):\n",
        "    score = sum(coverage[v] for v in subconstellation) / subconstellation_size\n",
        "\n",
        "    if score < score_threshold:\n",
        "        continue\n",
        "\n",
        "    subconstellations[frozenset(subconstellation)] = score\n",
        "\n",
        "print('# subconstellations after search space pruning: ',len(subconstellations))"
      ],
      "execution_count": 101,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "# subconstellations after search space pruning:  71972\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "HBw65fnTMnjU",
        "colab_type": "text"
      },
      "source": [
        "### Genetic Algorithm"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "mfm4ycqEACeI",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def init_pop(sol_per_pop):\n",
        "  population = []\n",
        "  for i in range(sol_per_pop):\n",
        "    constellation = [np.random.choice(list(subconstellations.keys())) for j in range(k)]\n",
        "    population.append(constellation)\n",
        "  return population"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2rrSXdB8_7Mj",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def cal_fitness(population):\n",
        "  fitness = []\n",
        "\n",
        "  for con in population:\n",
        "    coverage = sum([subconstellations[subcon] for subcon in con])\n",
        "\n",
        "    # penalty multiple subcons sharing the same satellite\n",
        "    for a, b in itertools.combinations(con, 2): \n",
        "      if not a.isdisjoint(b):\n",
        "        coverage-=1\n",
        "\n",
        "    fitness.append(coverage)\n",
        "      \n",
        "  return fitness"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "4mIZyOlm_7CP",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def select_mating_pool(population, fitness, num_parents):\n",
        "    # Selecting the best individuals in the current generation as parents for producing the offspring of the next generation.\n",
        "    parents = []\n",
        "    for parent_num in range(num_parents):\n",
        "        max_fitness_idx = fitness.index(max(fitness))\n",
        "        parents.append(population[max_fitness_idx])\n",
        "        fitness[max_fitness_idx] = -999\n",
        "    return parents"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "IheNmrMiAJpb",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def crossover(parents, offspring_size):\n",
        "    offsprings = []\n",
        "    # The point at which crossover takes place between two parents. Usually it is at the center.\n",
        "    crossover_point = np.random.randint(k)\n",
        "\n",
        "    for i in range(offspring_size):\n",
        "        # Index of the first parent to mate.\n",
        "        parent1_idx = i%len(parents)\n",
        "        # Index of the second parent to mate.\n",
        "        parent2_idx = (i+1)%len(parents)\n",
        "        offspring = parents[parent1_idx][:crossover_point]+parents[parent2_idx][crossover_point:]\n",
        "        offsprings.append(offspring)\n",
        "\n",
        "    return offsprings"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qobkEMrqAJnh",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def mutation(offspring_crossover):\n",
        "    # Mutation changes a single gene in each offspring randomly.\n",
        "    for idx in range(len(offspring_crossover)):\n",
        "        # The random value to be added to the gene.\n",
        "        random_idx = np.random.randint(N*k)\n",
        "        random_value = np.random.choice(list(subconstellations.keys()))\n",
        "        offspring_crossover[idx] = offspring_crossover[idx][:random_idx] + [random_value] + offspring_crossover[idx][random_idx+1:]\n",
        "    return offspring_crossover"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "V344ZW63AJjv",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "sol_per_pop = 50\n",
        "num_generations = 2000\n",
        "\n",
        "fitness_g = []\n",
        "new_population = init_pop(sol_per_pop)\n",
        "num_parents_mating = sol_per_pop // 2\n",
        "\n",
        "for generation in range(num_generations):\n",
        "    \n",
        "    # Measuring the fitness of each chromosome in the population.\n",
        "    fitness = cal_fitness(new_population)\n",
        "\n",
        "    # Selecting the best parents in the population for mating.\n",
        "    parents = select_mating_pool(new_population, fitness, num_parents_mating)\n",
        "\n",
        "    # Generating next generation using crossover.\n",
        "    offspring_crossover = crossover(parents, offspring_size=sol_per_pop-len(parents))\n",
        "\n",
        "    # Adding some variations to the offsrping using mutation.\n",
        "    offspring_mutation = mutation(offspring_crossover)\n",
        "\n",
        "    # Creating the new population based on the parents and offspring.\n",
        "    new_population = parents + offspring_mutation\n",
        "\n",
        "    fitness_g.append(max(fitness))\n",
        "\n",
        "# Getting the best solution after iterating finishing all generations.\n",
        "fitness = cal_fitness(new_population)\n",
        "best_match_idx = np.where(fitness == np.max(fitness))[0][0]\n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DYrKx9uVAJhl",
        "colab_type": "code",
        "outputId": "dff0f4b1-24f2-4a02-fe65-759250379cbb",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 72
        }
      },
      "source": [
        "print('Coverage :', max(fitness))\n",
        "print('Constellation :', new_population[best_match_idx])"
      ],
      "execution_count": 83,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Coverage : 1.004\n",
            "Constellation : [frozenset({0, 10, 15, 20, 28}), frozenset({2, 3, 11, 21, 23}), frozenset({0, 1, 10, 15, 20}), frozenset({4, 5, 14, 19, 25}), frozenset({7, 12, 17, 18, 26}), frozenset({8, 9, 13, 16, 24}), frozenset({6, 7, 12, 17, 26})]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "njXfr80IAJfH",
        "colab_type": "code",
        "outputId": "e1b52e9a-7bea-47f8-a1b3-50910db73fd7",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 282
        }
      },
      "source": [
        "import matplotlib.pyplot as plt\n",
        "\n",
        "plt.plot(fitness_g)"
      ],
      "execution_count": 84,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[<matplotlib.lines.Line2D at 0x7fc7462e44e0>]"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 84
        },
        {
          "output_type": "display_data",
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXIAAAD4CAYAAADxeG0DAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+j8jraAAAgAElEQVR4nO3dd5hU5dn48e+9HbbBukuRtvSqoiwoChZEwYJGo4km1kRRf2piTGJUEjVvNLG/MWpUTCxJNNG8scQKYkdFpAsC0ntZetu+z++PKTt9zsycKWf3/lwXFzPnnDnn3rOz9zxzn+c8jxhjUEop5VxZ6Q5AKaVUYjSRK6WUw2kiV0oph9NErpRSDqeJXCmlHC4nHQctLy83lZWV6Ti0Uko51ty5c3cYYyoCl6clkVdWVjJnzpx0HFoppRxLRNaFWq6lFaWUcjhN5Eop5XCayJVSyuE0kSullMNpIldKKYfTRK6UUg5nSyIXkYkislxEVorIrXbsUymllDUJJ3IRyQYeB84AhgAXi8iQRPerlFJOsmVvDQ1Nzd7nX2/cS11jk/f57978hque/4o1Ow7afmw7WuSjgJXGmNXGmHrgX8C5NuxXKaUyxruLtzJr9U7v84enL6fy1rc47eGP2bK3htF/+IA7Xl8CwKY9NUx6bCZ3vOZ6vnTLPv46cw0zlm5n/a5DtsdmRyLvBmzweb7RvcyPiEwWkTkiMqe6utqGwyqlVOpc+4+5XDR1lvf5nz5YCcCK7QeY8upiAD5Ytg2AvYcaAFi4cQ8AOw7UeV8nSYgtZRc7jTFTjTFVxpiqioqgoQKUUsqxauqbom/kliX2p3I7EvkmoIfP8+7uZUop1SbEkpuzktAktyORfwX0F5HeIpIHXAT814b9KqVUSu2vbaDR54JlKL5lEo+YGtlJSOQJj35ojGkUkRuAaUA28IwxZknCkSmlVJIcqGvkL5+u5oZT+vHKvE3sr2tkw65DPPf5WgDW3ntW2NdW3T0j4vpoklFasWUYW2PM28DbduxLKaXs9NnKHcxdt5uX52zgstG9GN2nnEmPzQSg8rBCbvnPooSPITE0s5NxsTMt45ErpVQ0jU3NZLsLyhLQil2wwdUbZHiPDgAcqm/k5a82cPnxlTQ1Gx5+71v+/NGqoH3+/u1l3HF2y20uBpOs8AHYcaCerzfu9VuWlYQiuSZypZTXofpGcrOzyM1uuXxW29BETX0TDU3NiAgNTc0c3qEd2/bV8sj7K5hy5mBG3jODBy44irOO7Bpx/1f/bQ7vfePqojeqsoyXrx0dcrsNuw4x9v4PAWifl033ju3YtLuGJf8zEYDvPP4Z0FICufutpbz45Xq+XLOLgtxsXp1vrb9FXna2pe1i5fnc2XGgjkmPzaQ4vyXVJuNipyZypdqIpmbDgdpGFm3aw5h+5X6tXGMML85ez5RXFzOmXzn/uOpY77rvP/UFCwNalWvvPYspr37NjKXb6d+piEP1TVz/4jwGdz2J7fvrOK7PYSFj8CRxgNlrd/mte33BJn76rwUsvPN01u5sufvxUH0T3247EPFn27ynBoB3Fm+Nchb8L0zmZofPqtOWbCUvJ4tTBnaKus/Alr0JaOjvr2v0jSDq/mKliVwphzHGYIzrK/rH31Yz7PAS7n5rKXPW7eL9m08mLye4M9pJD3zI1r211DW6emRcc2Ifju1TxrhBnQH4au1u700tM1fuYO2Og1SWFwIEJfGWOFz/+6alcQ99DIS+WLjnUH3En+upj1cDrtZ4Tpa1DnUH6xopzI8/je04ED6ma/4+F3D9LNX7g3uq+PpspeuOTyu18kztfqiUSpFZq3cy4Y+f0Of2t9lX28Dlz8zmnMc+49X5m9iwq4aXvlof8nXrdh7yJnGApz5ZzY+ea5k3t6bB/4aWkx/8yHJMgfXrcGLZp9VkN/TOaWzcHf8t77e/+rWl7UbeM8Pv+VMfB9ffwVrN3er5ioW2yJVyEN9bxPfVuG4D3+QuKwDUNkTuAx2OCawFxMBqXtrjvm3dilguCK7fdSiolJFsf3hnWWoPGIW2yJVyqGS07OKRjChi3WdzqjN5GJ7SSqp/NZrIlWpFkt2dLqQM+EDJkDxuSSLffsLRRK6UQ4VKCLHmCDuSSjLSeKxRpeUDLIJIp7U5CaFqIlfKoUIli1hzRJMNWcWuBrlvJLF+vjTHcGkgGYk0NtoiV0rZqDH9WS2ISOzfFJpi2D4ZpY1AkT7cknF4TeRKtSIhW+kRMocdFwmTkZhiLq3EEESmXBi1k3Y/VMqhQpdWYqub21FaSXQPNfVN3PfuMg763P0Yc2klhu3T/SUkGYfXRK5UhttxoI79tY08+9kav+VWL/BF2mrhhr0MPbyEA363kMco5EVX4+0e2dxs/G5G8nXFs7MZ06/cO3ys9/Vhot6+v5ZOxQV+y77ZvI+563ZbDjcVLfJIh0jG4TWRK5UCjU3N5LgHompuNhysb6S4IJfq/XU0NDXTpaSAD5Zt59TBnRARvtm8j1+/9jXz1u8Ju89QCaGmvomnPl7FVWP7eEcOjFR2uOSvX4ZdV9vQREFu9EGlQu39b1+s4/LjKwH44/sr+NP7K0K+9qPl1XRsn2dtp8ANL87n5Wv8B9q6+62lUWP023WMidQz0qIVVi78JqNGr4lcqQTsPlhPbWMTq7YfZE9NPaP7HMYbCzczum85by3azJMfr6bePePMEz88hutemEefikJWVx/k12cNDkpCD154FBeM6M6Zf/o06rFDtSwfdU8IXFGcz/nHdHdvF9/Ptnzrfo5yDxMbSai89NXaXYwb1Ikrnp3Nxt01wRv4CBypcP76Pby+IPTohbPX7OLmlxZEjSkSK4n0rUVbvI89Iy1asWVvLec+NjPs+DSgpRWlbLWvtoGGxmZyc7Kob2xmw65D1NQ3UdvYxLhBnWlsambIndPIzRLeuHGM34BQW/fW8uKX67wzqVtx3QvzAFhd7RrZL1RLctu+Wsv7e/zD0ON9ANz88kJufnkhr11/Asu27LO8T18ff1vtN1qhL99BpO56I3hCMAM889kaVlUfDFoXza9fWxxx/SsWh6gN58Hp30bd5voX58W9/0hJHDKwtCIiFwJ3AYOBUcaYOZFfoVTqNDUb9tc2UFyQizGGL9fsoktpAdX763h/6Tae/tRVcy7My6ah2VDvU8f908VHc3SPDtQ3NlOPqwTg67g/vJ/KHyWk/8zbGHWbWFqTgR5+L3zCG3nPDMYNcg3vGioxLduyj7cWxZ7E24LDikKUkhKUaIt8MXA+8JQNsSgVs+Zmw7z1u9m0p4b/m7uR564cxaMfrGDNjoO8vmAzAFeN6c2griX84t8LQ+7jYH1T0LKf/HM+n95yivd56+uwlrhILf14WuJtwcWjejCgc7Ht+00okRtjlkLmDN6j2p5/frXeO442uGqzf5zhf2HtjUWb6VgYeytI39aRbd5rvQykXC4e1TMp+03ZDUEiMllE5ojInOrq6ugvUMqCldsjzxwDkC2Skrv5lIomK0mtg6gtchGZAXQJsWqKMeZ1qwcyxkwFpgJUVVXpX5WyhaUZWeKckiVwKjSlMlXURG6MGZ+KQJSKx7Kt0XtkZGdJXD0FwqV/TeoqXslqketYK8rRPl+10+95qBybLZLwxUrf/ab7Fm/lXMm67pJQIheR80RkIzAaeEtEptkTllKRxXJLefylldDLY+nrrZSvtNXIIzHGvAq8alMsSkW1+2A9F02dxfJt+3nhqmMtvcZ1sTP2Y/nW333H/vjn7NATHNvh/aXbeOmrDUnbv0qvONsUUemdncoRjDEMvXMah3z6fM9es8vSa7OyJK4ZZNbsaOkL7ftBYMeIgeFEGltFOV9GllaUSpU/vb/SL4nHIt5W0MVPt8xY7ztreiyTGCiVCtoiVxnv+hfn+Q1iFMmug/VBy7Jt/j77yrzExvpQbZn2WlFtkDEmbBIP1S4ONdiRYO9ARb4DRimVCTSRq4zW0GRDBrah+6FSdtAauWqTahrC18XDTVYQSIdMUZkiWe9FrZGrjGSM4UBdI3URErlVYndtRakMoy1ylZH+/NEqjrhrOouiDNJvhaDD0KrMkKyRYjWRq4zkucC5fNv+hPelwyyr1k4TucpIntxrxwBVWllRmSJZTQpN5CojLdnsGtWwqTnKhhbMWbebRh3pSmUA7bWiWrVNe2p44ct1jLpnBl+ubhnR0K67KLfv14GuVOulvVZU2ngmRP5w2Xae+mS1d/n3p87y28YOVsdlUSqZrEyEEg9N5Col5q/fzYfLq7ngmO4s27qPl+dsZMbSbVFfZ9cAVRt319iyH6USkazSiiZylVR/+XQ1n67YwcffuuZpffazNeyvtT6WuA5QpewwvEcHFmxovSNLaiJXUa2qPsC7i7eyqvoAr8zbxItXH8vxfctDbrth1yHG3v9h2H3FksQBnvp4dfSNVJvWrUM7Nu2J/I3rkYuGc9IDH4VdX1KQQ1lhHmt3HrI5On96sVPZqr6xmdteWcTD733Ly3M28IV7yrR/zl7Pi1+u57JnZlN561u8Nn8Tpz70MQ9MW+4d9e8HT3/Jna8v9it7zFu/m9fmb+KCJz9Py8+jkuvtn4wNu25sf9eH+rNXjGT84E6pCokO7XPpWlrA8z8axdDDS8Jud/GonvQ6rJAzhrXMIf9/147222Zw1/CvT9QVx1d6H3cqLkjKMRJqkYvIA8AkoB5YBVxpjGm9318catu+Wv7+xTr+OXs9T106gh0H6rn2H3ODtlt771nc9srXfsseCTOeyfNfrKNTSQHXn9IPgPP/rAk80MkDKyjKz+FNi0PwRvLLCQN5YNrysOv/+P3hPPPZGu+dsMf3PSxoPtNAS/9nIoPveDdo+RM/PIYZS7fzn3kbAThtSGeGHF7Cmj+cSe/b3vbbVgRG9OrIpyt20L1jOwJ7Si/57QQ++baaicO6sGTzPs5+dKaVHxeALiUFbN1Xy9j+5Xy6YkfQ+oqifN67+SQAXrv+BJqaDYN+0/LzvP2TsfQuLyQ/x9Vevff8I3ln8VYAqirL+Nfk49hf20jH9rn071TMuY/P9L7u/mnL+Gh5td/xFtxxGpf+dTZfbwq+2/jdm8ZSVpjHQ9O+5aU5GzhxQAWfuMuJFcX5APx4TG/ycpLTdk60tPIecJsxplFE7gNuA36VeFjKDtX76xh5zwy/ZRc8+UVM+2iOUKN+YNpypi/Z2iovJL7z07Gc8cinCe0jJyuLx35wDG8ueito3YShnZm2ZBuXHNeTf8wKP3XckK4lfLNlH51LCoKSc7cO7SguyGHZ1v185+hu9OtUxNmPzuRvPxrFroP1YRP5y9eMJjtLaJeXzewppzLqnve5aGQPmo1h0lGHM7Z/BSN7l3kT+S9OHwj43yG7/O6JvLFwC8N7lNK7vIizj+xKv07FQccqzM/hjCO6AtCxMM/CWWvx8PeO4uH3vuXZK0bSb8o7Qet935m52VnkZsOVJ1Ty7GdrXecuoJVe2j6XkwZUeK/XHNfnsJDHbZeXzXNXjuK0hz9mxfYD3uXt83J448Yxftv+7s1vKCvMY1AX17HumDSExmbDb84eTPu8HPbU1JOfk8389buZfGKfmH7+WCQ6Z+d0n6ezgAsSC0fZ6eaXFyS8j0iJHGChDWOhZCI7vmrnRJjQ4qlLq9iw6xBdSgv495yN1DUG3/k099fjueftpXyzxXVz1KXH9fJLzp/dOo59tQ3sOuCaTGNYt1JW3nMGOdlZvL4g/OQXo3qXeR93Ki7g3ZvG0quskHZ52d7l5UX59O9U5JfIfOXnZHPBiO7e554k7sn1t585iLOPPNzvNdkBBeKPfnEyJz/4EQDt87I5VN/EXy6rYkSvjhigrDCP4/uFvhYDobum3jlpqDeRh/KXy6totDg08hs3jqGuoZmahibmrd8dsjX9m7OH+D0vzM/hoe8d5X3uKaX85fKRlo4ZLzsvdv4IeCncShGZDEwG6Nmzp42HVYG276/l85U7WepOAInQTiP+PC1kK7KzI1/Z6lHWPuL6wBnXQ40ZU1KQS0lBrvd5TnbsX909rclwYrlA59m0Z1khh3do57cuKyC0wPUAR3Qvtdxyj+et6Wm5W1GQm01Bbjal5HKm+1tFpoqayEVkBtAlxKopxpjX3dtMARqBF8LtxxgzFZgKUFVVpekhiS6aOovV1QfJjZJIrNBE7i+W0xHYAo1VVlZgIk9od2kXeD5C/TxO/xnTJWoiN8aMj7ReRK4AzgZONXbdhqcSsrraNfu7HbPr6K/UXyznI1JpxYrAlwe20J0mcO5U359HQiyLSt+aXon2WpkI3AKcZIxJbgdMZcmI371n6/70byV+gS3qWGVnifcXIAQn9kjSP3Rv8Dsn6BtGiFfFksj1vdki0Rr5Y0A+8J77jTPLGHNtwlEpy3YcqGP3wXoenL6cwV1L2BliFvlAWQJW73yPdrFThZdgHifLZ65REWeUHVqGHw5eF1zzD7WN9WPpt8UWifZa6WdXICq6usYmHpr+Lc99vpZv7z4DgJMf+IgDda67JactiT52Cbj+oKwmaB39NX6JDpBk5WJnMsXzq4/0Mwcmad+fx/M4lp9R35ot9BZ9BzDGsOtgPSPubukTfqi+kQO1jd4kHgtXgrD2Z6CNnvQJTHyJXjyNVzxHDfW2ybXQoyamErm+N700kTvAFc9+5b2JwWPSozNZ5b6oGavY/lj0ryVeiebdwIuD8XQDtEMs74BIMeZmZ/HZreM44d4Pwr8+hmOpFprIM9T2/bWUFORSvb8uKIkDcSdxiC0hWKm5tyWp/FwLLDNUHlaYuoMnKNx56hai7zi0JPBYTq/R4oqXJvIMNeqe9xnbvzwpQ2/WNtgwf5qKyo5KiO83oh5l7Vl01+kcedf0CK+wTypbx307FbFgw56YykfhPixm335qm7u2o4k8A+1yt4JDDRSk0itdrUBPfvO9i9PK9snQpyL8NwNvr5UYz9OzV4xk0aa9FOZbT0nhEnmnkuSMMJjJdBjbDDNtyVaOsbkvuFVaD/d30oCKBPcQfza97uS+QPw9M+yYUizUsb/5nwm889PwQ9rGe9yOhXkRz/fpQzrHtd+2QhN5GjU3Gw7VNzJzxQ7eWrSFaUu2cs3fg4eXTVk8msf9HN839Oh4qfCriYP8nseaIDu2d7XcJx11eJQto/M9cvu8HPJzLA5WYqM///CYlB/TSbS0kkS1DU38ccYKLqzqTueSAn7z2mLunDSE6d9s45b/W5Tu8II47eaf0na57K1piOk1g7oUs2zrfkvbJlqeiPX15UX57DhQl9hB3Y7vV86Tl4xg3KBOvLFwsy37tCTCDUGJyMnO4ubTBrB8237eco/vrt8gW2giT5IHpi3j8Q9XAfDkx6v41cRBvDp/E52K8/1mjM8kTkvkgd3zrHj3phOpvDV4fPBQQrWCYzlFnlf361TEpt011DQ0Rdw+P8QwqYn8SiYOCzXWXXLF0/vEqp+c2p+563a1JPIkHMOpNJEniSeJe7RcBMpcDsvjaRlEKp5T9N7PTgQIml0nUKTZY5xwe36qOe39mkyayFPE21LJ4Hef81rksW3/ZsDsLsnmSb5Wbzu3Y9jhtkT7kbfQi502qt5fxzmPzWTLXmdOfea0i52x3rI+rFuppe0GdC4CQreCC92z6Ez/2Yn8/LQBMR0/nPbufZa2y/X7P93iaXQUF7jahnkRPpRm334qM9xzbcYeU+jHbZ0mchu9PGcDizbu5fnP1wWtizQqXKYYdue0dIcQk0SHiQ3nvzeEbrmfMawLN47rz6AuxXQuKeC6k/vy+A/C96YI19NkZGVHv+f/vvZ4bjtjEH+86GjGD+7M57eOiz94G91+5mDKCvOizmQU+JpfThjIaUPC1+c7lRTQr1NRwvFl8J9SymlpxSZNzcY7y3mor3yeP2p989knWTXygjBzgT1xyQgAxvv0aT7ryK5c/2Lo/Yz0mRsT4PkfjWLtjoNcWNXdb3m/TkXexPaXy6v81tnxWdWtQzsO1rsGV9tzyHovn1MHd2beb06L6VjFBblcf0psg6KODjMJcjQ3je8f1+vCuf6Ufvzy/xbRuSTf1v2mgiZyGzQ2NfvP8h0iW3tyzl9nrklNUG3ACf3KWT87/Az00bx54xjOfnRm2PW+te1RlWVht/vVxEHc9+4yv2Wzp5zqnXjX46QBFTHfZPTrs4fQPj+HM4a1zBn5s/EDYro+MPNXpwCuO4Z3ZdjYOct+NzGmmZQqil1J9poT+/DDY3vZGsuFVT24sKqHrftMFS2t2GBltf9M4067aJgphvfoENP2vz1nqPexp64cS906Wi3aN708c2X4WdA9d2H6Ckzi8Sovyuf35x3h16Plp+P7c8M4661REUFEOKwon/6di22Jyy4FudkxTRjd67BCZtx8Er+cMDCJUTlPQolcRH4nIotEZIGITBeRxG8jc5DahiY27j7Ez19e6Lf81fnBN2Ckf+qtzNfO6vTmbr7J7c0bx/DkJSOCLtgeFmFG9h5l7XnzxjGcMjB0K/niUT29j4tiGANEJVe/TkUxJf+2INGz8YAx5khjzHDgTeAOG2JyhFmrdzLoN+8y5r4PWbJ5n986u+7Oa+2eunSE3/NQ1xbe//lJLPvdxLD7KM7P4VcTB9GjrD0Th3XhB8e2JN+JQ7swN0qNd1i3Up65YiSf/PKUoHXt8mK/Fb19HK9RKlGJTvXmm8EKaeXX8nYfrOeh95YzfnBnrnj2q5he+7s3v0lSVM51eGnL2NTDupUw5cwhTHrMv2bdt8K/d8MR3Uqpa2xiTD9XK/rr307wW19RnM/jPziG61+c570u8Z/rjmdvTUttuKwwz69WLCL0PMzVM8O3FQ6uboaxfJf64Ocns2mPzkOuUivh74sicg9wGbAXCG7WtGw3GZgM0LNnz3CbZbSj3aMS/mNW/BfYMkGPsnZs2BVfX/eBnYtZvs3aWCW+jurRgYUBY6v7VpvevNF/RL3Xrz+BDu2Da9hvWLipx9Oy9+x/RC//7n5f3DYuZDfQtfeeFbRsQIw15S6lBXQpbXvDqKr0ilpaEZEZIrI4xL9zAYwxU4wxPYAXgBvC7ccYM9UYU2WMqaqoSHR40NRbtNH+CR7SpSCB0ev6d46v/2+ojgmRrgkf1aMDvRKcESdcP+78nOywXQyVcqKoLXJjzHiL+3oBeBu4M6GIMtQ5j32W7hBsk0j/63SMb6KUiizRXiu+faDOBZaF21ZljkRysRPyuLel74BYlbJDojXye0VkINAMrAOuTTykzPNNQK+Utsze2dmTc21c87hqaxLttfJduwLJZOc8Fv7uPydKpE+7E0ormTzCpFLJoL3qLWh02rCAUSQyfoedNzZpvlXKHprI26BEcnGSBhxMCr2bVrUVet9xBBt2HYrr7r7WLF258clLRtC73Fp3RE9LX9O4ais0kUcw9v4P0x1CUmRS98MZN59kaUS+eOaf1Aa5ais0kQcwxnD9i/PYvKc23aEkTSL5LVK54qoxvflLDMP0GrBlgoHg/aa++H5Mzw5URRjqVqlk0kTutvtgvfcW/FYvgaZqpJf++uwhXDq6Fyc98FHI9f++djQXPvmF93myepeko7Tyyv87IYVHU8pfm0zkxhg+W7mTLXtr6FRSwBXPzm5TPSgSSXCxzpPpa2SKWqwd27uGru3aoV2ULZVqHdpUIl+74yCX/PVLNu7O/MmRB3UpZtnW2AensiKRnic5Dpjp/eSBFTx68dFMGBp7XV0pJ2oTibyusYmBv3433WFYlpMldC0tSFoiT6RbXp4DBvQXESYd1abmOFFtXOb/Vdrg/D9/nu4QYmJ1dvjbzhiU5EiCBbbIH7louN/zcCMOhhKqmvXCVcfyzk/HhlijlAqnTbTIA2fwaS0Cx9m2KpHSSnaW/2f/ucO7sftgPX3dvU96lLXj6rG9eWfx1qglrFDXJU7oVx5/cEq1UW2iRe40VhNtvBWSWFrNgXJDBHfFCb0Z27/CHZMw5awhzPzVOM48QmvUSqWCJvIMZD3Rxp3J42a17GNFvwr7+5Ar1Ra1idJKaxVvizyRXHxk91LL20a6qBpqWjWlVHy0RZ6BIiXoXu5JgiH+hrXVFn/HgDkzv7htHGP7V/Dez0609Po7Jw1hUBfXnJe+vV0GxjgPplIqMk3kDvPRL072PhYR2uVm07citrktrbbkj+jewe95V/es9/0tJuJOxQW8/ZOx3HBKPx656GgAZt9+Kq9ef7z1YJVSUbXqRF7f2MyZj3ya7jBiVpCbTW6Y/toiwhHdXOUNARbeeTrTbrLWQva4amxv7+M3bhjD2nvPok+IkQW7dSjw++CIR1aW8IsJA70zy3cqKaB9nlb0lLKTLX9RIvJz4EGgwhizw4592mHJ5r18s8V5XQ8L87O557wjmP7NtpDrPTVuA+TlWP8s/t/vH8U5R3UjO0uCatT3XXAkFz75BVeP7c3Tn7oGvrrj7KG0y8vmlxMGsnDDHr/tvzP8cE4cUGH9h1JKJU3CiVxEegCnA+sTD8deDU3OHEDlhL7lVBTnc+lxvfj7rHXe5SUFrl+X5yJis09H7LycLOobmyPu97yju4ddN7KyjLX3nsXcdbt4+tM1jKos847Ffv0p/YK2/6O7VKKUSj87WuT/C9wCvG7DvmwVLbFlmoV3nM6G3YcY4K5Bj+lfzt9nreP+C47kpAEVFOS6Equnxu07euAr1x3Pq/M3MbKyjGv/MTdo31Zb7iN6lfHZrePopgNOKeUYCSVyETkX2GSMWRht/A4RmQxMBujZs2cih7WsoclZiby0fS6l7Vu6900Y2oXFv51AUb7/r8lzpn3vjBzWrZRh3UJ3DVz82wkxdTnUJK6Us0RN5CIyAwh1i94U4HZcZZWojDFTgakAVVVVKal5HKhrTMVhkiowiUPLLD1WT2KofSilWo+of+HGmPGhlovIEUBvwNMa7w7ME5FRxpittkYZp2+3JWf0wHTzJnJnXgJQStks7qaaMeZroJPnuYisBaoypdeKMYZHP1iZ7jCSI0SNXCnVdrXafuSfrsiIz5Ok8JS7mzWPK6WwcawVY0ylXfuyw0tzNqQ7hKTx9lpJwyTDSqnM02pb5G8t2pLuEJImS1L+s/0AABBESURBVHzuCFJKtXmtNpG3ZprHlVK+WmUi33OoPt0hJJVn9MJmvdiplKKVJvInPlqV7hCSytMi14udSilohYm8qdnw1Cer0x1GUrX0I9dMrpRqhYl8f21DukNIumg18vKiPIr1bk6l2oxW99e+qvpgukOIy4/H9I6+kZt32JQwmfzL28djjKHflHcSjksplflaTYt8+75aXpu/ie8+8XnSjvH7846IuD7cmCaf3nJK2NeUtnNNp3b12D6W4xjd9zAAuncMPbhVdpaQE2ZiCqVU69MqWuTrdx7ixAc+TPpxupTmR1zfv3MR89f7T8Bw6XG96FHWPswroCA3i701scVx9dg+nHlEV7p3DL9fj7LCvNh2rpRynFbRbNu0J8ZMGKd2ua7PvYtH9WBUZZnfun/8+Fjv439fO5ohXUsAGNXbfzuALiUFCcUhIpaS+Ls3jWW6xYmSlVLO1SoS+cVPz0ravn3LJcf1KeOBC47kjrOHBm1XWd6SWLNE6O2eAzPUMO3H9OoQvDAJBnUpobwo8rcIpZTztYpEnky+iVxEuLCqh3cKNF+BE2voOChKqVRpFTXyZGoyhr/9aBTdwlxY9BWqW7cQ3CS/YER33v46I4ZsV0q1Am2iRX7NSdZ7hARqbjacOKCCvhVFMb3Ok9QDSytr7z2LcYM6xx2PUkoFahOJ/ObTBsT92iaLd08aY/yStjeRx31kpZSypk0k8lDljVB+emr/oGVNYQY0CVUDP9w9aXH7vGzLNfJJRx4OQFGBVrmUUvFpE9kjVM+RUI7uGdybZHgP6z1M7vvukUwc2oXB7q6HkWSJa9Cr284czI3j+usEyUqpuCWUPUTkLuBqoNq96HZjzNuJBhWLnQfqom5jtbyRneW/ZZbAE5eMCLPP4L0W5ecw6ShXCzuwRv7ABUfStbTlgunXd02g2Riys4TS9rkWI1RKqWB2NAP/1xjzoA37ics1f58bdZvAroHhZAVsd0S30rhbynedM5R2edmcPNA1P/WFVT381hdqC1wpZRPHZ5OV1QeibmO1RR6YyGPpCR54TfTwDu145KKjY9iDUkrFx46LnTeIyCIReUZEOobbSEQmi8gcEZlTXV0dbrOYNDcb9hyKPmyt1Rp5YGklEr3hRymVKaImchGZISKLQ/w7F3gC6AsMB7YAD4XbjzFmqjGmyhhTVVFRYUvwX63dZWk766UV/+c6b4NSygmillaMMeOt7EhEngbeTDgii4wxfH9q7GOsfHHbOEb/4QO/ZZ4eJFlZ1m+z1ySvlMoUCZVWRKSrz9PzgMWJhWPdxt3xjXjo23PEw5OTs63WYNAZ7JVSmSPRi533i8hwXHltLXBNwhFZtHjTXtv25WldB13sjJCtdb5MpVSmSCiRG2MutSuQWO06VG/7PrMCvp9ETOS2H10ppeLj2Fv0Gxqbbd9nYK+VSMk6MMlrA10plS7OTeRN9mfOwNKKUko5gXMTebN9LfLnrhzJxKFdgm4cilQHD1yj/cqVUuni2Ds7GxrtS5wnD+zEyQM7sXL7fr/lF4zoHv5FWktRSmUI57bIm+Jvkd97/hFRt/lqynh+PKZ32PWBadzqULlKKWU3xybymoamuF970aie/HLCwBBrWpJxcUFOxDtCgy52amlFKZUmjk3k63YeSuj1zSEmjPDk7fKifApygydY9hWYuEvb6VC0Sqn0cGwi31uTWD/yUBP/eNrfxTHO1jPn1+Pp0D4voXiUUipejk3k+2oaI67/wbE9I64f1LU47Dord236blJelB91e6WUShbH9lrZVxt5+Nrfn3cE5x3djVmrdoZcP2Fol6Blnpq4lWq3dlpRSmUKxybyvTUNlBTksK82fMt8ZGUZIyvLAJj+sxNpF6XuHUu/E83jSqlM4chE3tDUzKH6Jrp3bBcxkfsa0Dl8KSWQlda2p/zyr8nHWd6vUkolgyMT+X538i4pyAXiG842lO4d23F838P42WkDLL/GFYNSSqWPIxP5wo17ACjMj1wqiVVOdhYvXh1bC1uHZ1FKpZsje63sPujqenhU9w5pi2FYt1IASrT/uFIqzRzZIvdMuNypJH3d/u7+zjAuOa4X3ToEzziklFKp5MgWeb17nJVod18mU0FuNsN7pO8bgVJKeSScyEXkRhFZJiJLROR+O4KKptndY0THD1dKqQRLKyJyCnAucJQxpk5EOtkTVmRTP1kNBM/oo5RSbVGiLfLrgHuNMXUAxpjtiYcUWV1jk7dGHsus90op1VolerFzADBWRO4BaoFfGGO+CrWhiEwGJgP07Bl5HJRIZq7Y4bPPuHcDwJs3jmHbvtrEdqKUUmkWNZGLyAwgeGASmOJ+fRlwHDASeFlE+pgQo04ZY6YCUwGqqqrivsP9x8/P8Y0t5DbdO1rrSTKsW6m3G6FSSjlV1ERujBkfbp2IXAe84k7cs0WkGSgHqu0LMbxQafyy0b24ZeKgVBxeKaUyQqI18teAUwBEZACQB+yI+Iok61xSQFG+I7vHK6VUXBLNeM8Az4jIYqAeuDxUWSVZ9FqnUkolmMiNMfXAJTbFYgtN7kqptsaRd3Z6aNJWSimHJ3KllFIOS+RWyu8S0zw/SinlfA5L5OmOQCmlMo+jEnlzQCYP1frWurlSqq1xWCL3f65JWymlHJfIw9dWJp/YBwh9t6dSSrVmjkrkkWrkKbwPSSmlMoqjEnmkFrmHlluUUm2NYxP52P7laYxEKaUyh8MSecvj564c5beuvMg1EXPH9nmpDEkppdLOUcMENvtk8uws8RuP/MdjelNelM95R3dLR2hKKZU2zkrk7tLKb88ZCvj3UMnJzuK7I7qnISqllEovR5ZWdM5lpZRq4ahE7ulimOXO5DpNm1JKOSyRt7TIXYm8d3lhGqNRSqnM4LBE7m6Ra2lFKaW8ErrYKSIvAQPdTzsAe4wxwxOOKgxPIhe960cppbwSnert+57HIvIQsDfhiCKobWgGIC/bUV8klFIqqWzpfiiuJvL3gHF27C+cXQfrASgrbLnp55ieHdi+vy6Zh1VKqYxmVz/yscA2Y8yKcBuIyGRgMkDPnj3jOsjB+kYAigpawn7l/50Q176UUqq1iJrIRWQG0CXEqinGmNfdjy8G/hlpP8aYqcBUgKqqqriGKvR0P8zWGrlSSnlFTeTGmPGR1otIDnA+MMKuoMJZv/MQ0NL9UCmllD3dD8cDy4wxG23YV0R//mgVAFl6rVMppbzsSIkXEaWsYhdPQ1xb5Eop1SLhi53GmCtsiMMSz2TL2XpHkFJKeTmqSNHSIk9vHEoplUkclcg99M5OpZRq4ahE7knf2v1QKaVaOCqRe+jFTqWUauGoRO4pqWgeV0qpFo5K5EoppYJpIldKKYdzVCL3lFRMXCO1KKVU6+TMRI5mcqWU8nBUIi/Mc92IKujVTqWU8rBrPPKUePqyKl6dv4keZe3SHYpSSmUMRyXyHmXt+cmp/dMdhlJKZRRHlVaUUkoF00SulFIOp4lcKaUcThO5Uko5XEKJXESGi8gsEVkgInNEZJRdgSmllLIm0Rb5/cBvjTHDgTvcz5VSSqVQooncACXux6XA5gT3p5RSKkaJ9iO/CZgmIg/i+lA4PtyGIjIZmAzQs2fPBA+rlFLKQ0yUEahEZAbQJcSqKcCpwMfGmP+IyPeAycaY8VEPKlINrIsjXoByYEecr00mjSs2GldsMjUuyNzYWmNcvYwxFYELoybySERkL9DBGGPENevDXmNMSbTXJUJE5hhjqpJ5jHhoXLHRuGKTqXFB5sbWluJKtEa+GTjJ/XgcsCLB/SmllIpRojXyq4FHRCQHqMVdA1dKKZU6CSVyY8xMYIRNsVg1NcXHs0rjio3GFZtMjQsyN7Y2E1dCNXKllFLpp7foK6WUw2kiV0oph3NUIheRiSKyXERWisitKTxuDxH5UES+EZElIvJT9/K7RGSTe6yZBSJyps9rbnPHuVxEJiQ5vrUi8rVnzBv3sjIReU9EVrj/7+heLiLyJ3dsi0TkmCTFNNDnvCwQkX0iclM6zpmIPCMi20Vksc+ymM+PiFzu3n6FiFyepLgeEJFl7mO/KiId3MsrRaTG57w96fOaEe7f/0p37AnNhRgmrph/b3b/vYaJ6yWfmNaKyAL38lSer3D5IXXvMWOMI/4B2cAqoA+QBywEhqTo2F2BY9yPi4FvgSHAXcAvQmw/xB1fPtDbHXd2EuNbC5QHLLsfuNX9+FbgPvfjM4F3AAGOA75M0e9uK9ArHecMOBE4Blgc7/kByoDV7v87uh93TEJcpwM57sf3+cRV6btdwH5mu2MVd+xnJCGumH5vyfh7DRVXwPqHgDvScL7C5YeUvcec1CIfBaw0xqw2xtQD/wLOTcWBjTFbjDHz3I/3A0uBbhFeci7wL2NMnTFmDbASV/ypdC7wvPvx88B3fJb/zbjMAjqISNckx3IqsMoYE+lu3qSdM2PMJ8CuEMeL5fxMAN4zxuwyxuwG3gMm2h2XMWa6MabR/XQW0D3SPtyxlRhjZhlXNvibz89iW1wRhPu92f73Gikud6v6e8A/I+0jSecrXH5I2XvMSYm8G7DB5/lGIifTpBCRSuBo4Ev3ohvcX4+e8Xx1IvWxGmC6iMwV15g2AJ2NMVvcj7cCndMUG8BF+P+BZcI5i/X8pOO8/QhXy82jt4jMF5GPRWSse1k3dyypiCuW31uqz9dYYJsxxvemxJSfr4D8kLL3mJMSedqJSBHwH+AmY8w+4AmgLzAc2ILrq106jDHGHAOcAVwvIif6rnS3PNLSz1RE8oBzgH+7F2XKOfNK5/kJR0SmAI3AC+5FW4CexpijgZuBF0UkqcNhBMi431uAi/FvLKT8fIXID17Jfo85KZFvAnr4PO/uXpYSIpKL65f0gjHmFQBjzDZjTJMxphl4mpZSQEpjNcZscv+/HXjVHcc2T8nE/f/2dMSG68NlnjFmmzvGjDhnxH5+UhafiFwBnA380J0AcJcudrofz8VVfx7gjsG3/JKUuOL4vaXyfOUA5wMv+cSb0vMVKj+QwveYkxL5V0B/EentbuVdBPw3FQd219/+Ciw1xjzss9y3tnwe4Lma/l/gIhHJF5HeQH9cF1iSEVuhiBR7HuO6WLbYHYPnqvflwOs+sV3mvnJ+HK6BzraQPH4tpUw4Zz7Hi+X8TANOF5GO7rLC6e5lthKRicAtwDnGmEM+yytEJNv9uA+u87PaHds+ETnO/T69zOdnsTOuWH9vqfx7HQ8sM8Z4SyapPF/h8gOpfI8lcrU21f9wXe39Ften65QUHncMrq9Fi4AF7n9nAn8HvnYv/y/Q1ec1U9xxLifBq+JRYuuDq0fAQmCJ57wAhwHv4xrIbAZQ5l4uwOPu2L4GqpIYWyGwEyj1WZbyc4brg2QL0ICr7vjjeM4Prpr1Sve/K5MU10pcdVLP++xJ97bfdf9+FwDzgEk++6nClVhXAY/hvmPb5rhi/r3Z/fcaKi738ueAawO2TeX5CpcfUvYe01v0lVLK4ZxUWlFKKRWCJnKllHI4TeRKKeVwmsiVUsrhNJErpZTDaSJXSimH00SulFIO9/8BlRgGCdseVjEAAAAASUVORK5CYII=\n",
            "text/plain": [
              "<Figure size 432x288 with 1 Axes>"
            ]
          },
          "metadata": {
            "tags": [],
            "needs_background": "light"
          }
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "0_9-m3WXNYTh",
        "colab_type": "text"
      },
      "source": [
        "### Quantum Annealing"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "XqzhStbzpks2",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "s = set()\n",
        "for con in new_population:\n",
        "    for subcon in con:    \n",
        "      s.add(subcon)\n",
        "\n",
        "subcons = {i:subconstellations[i] for i in list(s)}"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "OR6N5mO35_Gj",
        "colab_type": "code",
        "outputId": "1f3fbd40-cede-4348-c668-c2a9a7db7495",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "len(subcons)"
      ],
      "execution_count": 86,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "56"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 86
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Qy0Iem4MNygQ",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "bqm = dimod.BinaryQuadraticModel.empty(dimod.BINARY)\n",
        "bqm.add_variables_from(subcons)    "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "OVdhHGdAlsQ8",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "for c0, c1 in itertools.combinations(bqm.variables, 2):\n",
        "    if c0.isdisjoint(c1):\n",
        "        continue\n",
        "    bqm.add_interaction(c0, c1, 2)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "r0AgXV5rlvqE",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# choosing num_constellations variables \n",
        "bqm.update(dimod.generators.combinations(bqm, k))"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "rLtpH7d7YadW",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# sample from the bqm using simulated annealing\n",
        "sampleset = neal.Neal().sample(bqm, num_reads=100).aggregate()\n",
        "\n",
        "constellations = [constellation\n",
        "                  for constellation, chosen in sampleset.first.sample.items()\n",
        "                  if chosen]"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "7EMss043NflA",
        "colab_type": "code",
        "outputId": "65e3b357-2735-460d-a0a7-9979ef906b4a",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 72
        }
      },
      "source": [
        "print('Coverage : ', sampleset.first.energy)\n",
        "print('Constellation : ', constellations)"
      ],
      "execution_count": 91,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Coverage :  3.102000000000544\n",
            "Constellation :  [frozenset({6, 7, 12, 17, 26}), frozenset({4, 5, 14, 19, 25}), frozenset({1, 20, 22, 28, 29}), frozenset({0, 2, 11, 15, 23}), frozenset({8, 9, 13, 16, 24})]\n"
          ],
          "name": "stdout"
        }
      ]
    }
  ]
}